136- كورس لغة بايثون Python شرح هياكل البيانات في بايثون – Python Data Structures – Radix Sort

مقدمة حول Radix Sort في بايثون

تُعتبر خوارزمية Radix Sort واحدة من خوارزميات الترتيب الفعّالة التي تُستخدم لترتيب الأعداد الصحيحة. تعتمد هذه الخوارزمية على توزيع الأرقام إلى مجموعات بناءً على الأرقام الفردية (الوحدات، العشرات، المئات، إلخ) بشكل متكرر. ما يميز Radix Sort هو أنه يمكنها ترتيب الأعداد في وقت خطي تقريبًا بالنسبة لعدد العناصر وعدد الأرقام في الأعداد، مما يجعلها خياراً مناسباً في حالات معينة عند التعامل مع مجموعات بيانات كبيرة.

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

كيفية تنفيذ Radix Sort في بايثون

لنفهم كيفية عمل Radix Sort بشكل عملي، سنقوم بكتابة كود بايثون يوضح ذلك. في البداية، نحتاج إلى دالة فرعية تقوم بترتيب الأرقام بناءً على خانة رقمية معينة باستخدام Counting Sort، ثم نستخدم هذه الدالة لترتيب الأرقام على مستوى الخانات المختلفة.

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array:", arr)

في هذا المثال، يتم استخدام دالة `counting_sort_for_radix` لترتيب الأعداد استنادًا إلى رقم معين (مثل الآحاد أو العشرات)، وذلك باستخدام الأساليب التقليدية للـ Counting Sort. ثم تقوم دالة `radix_sort` بتكرار هذه العملية لكل خانة رقمية، بدءًا من الآحاد وصولًا إلى الخانة الأكثر أهمية.

أمثلة عملية على Radix Sort

لنعرض بعض الأمثلة العملية على كيفية استخدام Radix Sort لترتيب قوائم مختلفة من الأعداد:

مثال 1:

arr1 = [123, 456, 789, 101, 202, 303]
radix_sort(arr1)
print("Sorted array:", arr1)

في هذا المثال، تحتوي القائمة على أعداد مكونة من ثلاث خانات، وتقوم Radix Sort بترتيبها بشكل تصاعدي بكفاءة.

مثال 2:

arr2 = [1, 4000, 300, 20, 5, 100000]
radix_sort(arr2)
print("Sorted array:", arr2)

في هذا المثال، تظهر فعالية Radix Sort في ترتيب الأعداد التي تختلف بشكل كبير في عدد الخانات، حيث يتم ترتيب الأعداد من الأصغر إلى الأكبر بغض النظر عن طول الرقم.

تُظهر هذه الأمثلة كيف يمكن لخوارزمية Radix Sort أن تكون أداة قوية وفعّالة في ترتيب الأعداد، خاصة عندما يكون لديك مجموعة كبيرة ومتنوعة من الأرقام التي تحتاج إلى ترتيبها بسرعة.