الترتيب الأساسي Radix Sort

الصياغة

place = 1
while max_num // place > 0:
    arr = counting_sort_by_digit(arr, place)
    place *= 10

📄 مثال

def radix_sort(arr):
    if not arr:
        return arr
    max_num = max(arr)
    place = 1
    while max_num // place > 0:
        arr = counting_sort_by_digit(arr, place)
        place *= 10
    return arr

def counting_sort_by_digit(arr, place):
    output = [0] * len(arr)
    counts = [0] * 10
    for num in arr:
        counts[(num // place) % 10] += 1
    for i in range(1, 10):
        counts[i] += counts[i - 1]
    for num in reversed(arr):
        digit = (num // place) % 10
        counts[digit] -= 1
        output[counts[digit]] = num
    return output

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

أهم النقاط

💡 نصائح عملية

• تأكّد أن خوارزمية الترتيب الفرعي بكل مرور (عادة Counting Sort) مستقرّة — هذا شرط أساسي لصحة Radix Sort ككل

⚠️ أخطاء شائعة

• استخدام خوارزمية غير مستقرّة كخطوة فرعية بكل مرور — يكسر الترتيب الذي حقّقته المرورات على الخانات الأقل أهمية

خصائص ذات صلة