خوارزمية Radix Sort في بايثون - شرح مبسط خطوة بخطوة مع الأمثلة

🔢 خوارزمية Radix Sort في بايثون: السر في الفرز حسب الأرقام!

مرحباً بك في درس جديد من دروس خوارزميات الفرز! بعد أن تعرفنا على خوارزميات مثل Bubble Sort و Merge Sort، حان الوقت للتعرف على خوارزمية ذكية وفعالة تعمل بطريقة مختلفة تماماً: خوارزمية Radix Sort أو "الفرز حسب الأساس". 🧮

تعتبر Radix Sort من الخوارزميات غير المقارنة (Non-comparison Sort)، أي أنها لا تقارن العناصر مع بعضها البعض مباشرة مثلما تفعل معظم الخوارزميات الأخرى. بدلاً من ذلك، تعتمد على فكرة الفرز حسب الأرقام الفردية التي تتكون منها الأعداد.

🤔 ما هي فكرة Radix Sort الأساسية؟

تخيل أن لديك مجموعة من الأرقام مكتوبة على أوراق. كيف يمكنك ترتيبها بسرعة؟ إحدى الطرق الذكية هي:

1. رتبهم أولاً حسب الآحاد (الرقم في أقصى اليمين).
2. ثم رتبهم حسب العشرات.
3. ثم رتبهم حسب المئات... وهكذا.

هذه هي الفكرة الأساسية لـ Radix Sort! تُعرف هذه الطريقة بـ LSD (Least Significant Digit)، أي نبدأ من أقل رقم معنوي (الآحاد) ونصعد نحو أكثر رقم معنوي (المئات، الآلاف...).

مثال بسيط: لترتيب الأرقام [170, 45, 75, 90, 802, 24, 2, 66]

• الخطوة 1 (الآحاد): نرتبهم حسب الرقم الأخير: [170, 90, 802, 2, 24, 45, 75, 66]
• الخطوة 2 (العشرات): نرتبهم حسب الرقم الثاني: [802, 2, 24, 45, 66, 170, 75, 90]
• الخطوة 3 (المئات): نرتبهم حسب الرقم الأول: [2, 24, 45, 66, 75, 90, 170, 802] أصبحت القائمة مرتبة! ✅

⚙️ كيف تعمل خوارزمية Radix Sort خطوة بخطوة؟

لتنفيذ Radix Sort، نحتاج إلى مساعد صغير: خوارزمية فرز مستقرة (Stable Sort) مثل Counting Sort. لماذا؟ لأننا نحتاج إلى الحفاظ على الترتيب النسبي للعناصر التي لها نفس الرقم في الخانة التي نرتب حسبها.

خطوات التنفيذ:

1. أوجد أكبر رقم في القائمة. نحتاج لمعرفة عدد المرات التي سنكرر فيها عملية الفرز (عدد الخانات في أكبر رقم).
2. لكل خانة (من الآحاد إلى أكبر خانة)، قم بما يلي:
   • استخدم خوارزمية فرز مستقرة (مثل Counting Sort) لفرز القائمة بناءً على تلك الخانة المحددة فقط.
3. بعد الفرز حسب آخر خانة (أعلى خانة)، تصبح القائمة مرتبة بالكامل.

💻 تنفيذ Radix Sort في بايثون مع مثال بسيط

لننفذ خوارزمية Counting Sort البسيطة أولاً كمساعد، ثم نستخدمها داخل Radix Sort.

# دالة مساعدة: Counting Sort المعدلة لفرز حسب خانة معينة (digit)
def counting_sort_for_radix(arr, digit_place):
    """
    يرتب القائمة بناءً على رقم محدد (مثل الآحاد أو العشرات).
    arr: القائمة المراد ترتيبها
    digit_place: قيمة الخانة (1 للآحاد، 10 للعشرات، 100 للمئات، ...)
    """
    n = len(arr)
    output = [0] * n  # قائمة مخرجات بنفس طول القائمة الأصلية
    count = [0] * 10  # قائمة عداد من 0 إلى 9 (لأن الأرقام من 0-9)

    # 1. عد تكرار كل رقم في الخانة المحددة
    for num in arr:
        # استخرج الرقم الموجود في الخانة المطلوبة (مثل رقم الآحاد)
        current_digit = (num // digit_place) % 10
        count[current_digit] += 1

    # 2. اجعل قائمة العداد تراكمية
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 3. بناء قائمة المخرجات (من الأخير إلى الأول للحفاظ على الاستقرار)
    for i in range(n - 1, -1, -1):
        num = arr[i]
        current_digit = (num // digit_place) % 10
        output[count[current_digit] - 1] = num
        count[current_digit] -= 1

    # 4. نسخ قائمة المخرجات إلى القائمة الأصلية
    for i in range(n):
        arr[i] = output[i]


# الدالة الرئيسية: Radix Sort
def radix_sort(arr):
    """
    يرتب قائمة من الأعداد الصحيحة غير السالبة باستخدام خوارزمية Radix Sort.
    """
    if len(arr) == 0:
        return arr

    # 1. أوجد أكبر رقم لمعرفة عدد الخانات
    max_num = max(arr)

    # 2. كرر عملية الفرز لكل خانة (من الآحاد إلى أكبر خانة)
    digit_place = 1  # نبدأ من خانة الآحاد (1)
    while max_num // digit_place > 0:
        counting_sort_for_radix(arr, digit_place)
        digit_place *= 10  # انتقل للخانة التالية (عشرات، مئات، ...)

    return arr


# مثال على الاستخدام
if __name__ == "__main__":
    my_list = [170, 45, 75, 90, 802, 24, 2, 66]
    print("القائمة الأصلية:", my_list)

    sorted_list = radix_sort(my_list.copy())  # نستخدم .copy() لحفظ القائمة الأصلية
    print("القائمة بعد Radix Sort:", sorted_list)

📊 شرح مخرجات المثال

عند تشغيل الكود أعلاه، ستكون النتيجة:

القائمة الأصلية: [170, 45, 75, 90, 802, 24, 2, 66]
القائمة بعد Radix Sort: [2, 24, 45, 66, 75, 90, 170, 802]

لاحظ كيف تم ترتيب الأرقام من الأصغر إلى الأكبر بشكل صحيح! الخوارزمية عملت في الخفاء على فرز الأرقام حسب الآحاد أولاً، ثم العشرات، ثم المئات.

⚡ مميزات وعيوب Radix Sort

المميزات:

• سرعة وكفاءة في ظروف معينة، خاصة مع الأعداد الكبيرة عندما يكون نطاقها محدوداً.
• تعقيد زمني خطي تقريباً: O(d * (n + k))، حيث n عدد العناصر، k نطاق الأرقام (عادة 10)، و d عدد الخانات في أكبر رقم.
• مستقر (Stable)، مما يحافظ على الترتيب النسبي للعناصر المتساوية.

العيوب والقيود:

• تعمل فقط على الأعداد الصحيحة أو البيانات التي يمكن تمثيلها كأرقام (مثل السلاسل بنفس الطول).
• تستهلك ذاكرة إضافية بسبب استخدام Counting Sort المساعد.
• قد لا تكون الأفضل إذا كان نطاق الأرقام كبيراً جداً مقارنة بعددها.

🧪 جرب بنفسك: تمرين سريع

حاول تعديل الكود السابق ليعمل مع القائمة التالية، ثم تأكد من النتيجة:

test_list = [432, 8, 530, 90, 88, 231, 11, 45]
# قم باستدعاء radix_sort() عليها واطبع النتيجة

🎯 ملخص الدرس

تعلمنا اليوم خوارزمية Radix Sort، وهي خوارزمية فرز ذكية تعتمد على فكرة الفرز حسب كل خانة على حدة، بدءاً من الآحاد (LSD). تعمل باستخدام خوارزمية فرز مستقرة مساعدة (مثل Counting Sort) وتتميز بكونها سريعة وكفؤة مع أنواع معينة من البيانات الرقمية. تذكر أنها مناسبة للأعداد الصحيحة غير السالبة بشكل أساسي.