الترتيب اللامقارَن: Counting Sort وRadix Sort

المشكلة: هل يمكن الترتيب أسرع من O(n log n)؟

كل خوارزميات الترتيب التي مرّت معك (فقاعي، إدراجي، Merge، Quick) تعتمد على مقارنة عنصرين ببعضهما (arr[i] > arr[j]) — وهذا النوع من الخوارزميات له حد نظري أدنى مثبَت: لا يمكن لأي خوارزمية مقارنة أن ترتّب أسرع من O(n log n) بأسوأ حالة. لكن ماذا لو لم نقارن العناصر إطلاقًا؟ لأنواع معيّنة من البيانات (أعداد صحيحة بمدى محدود)، هذا ممكن فعلًا — وهذا بالضبط ما تفعله Counting Sort وRadix Sort.

الترتيب بالعدّ (Counting Sort)

الفكرة: بدل مقارنة العناصر، عُدّ تكرار كل قيمة، ثم استخدم هذا العدّ مباشرة لحساب موضع كل عنصر بالمصفوفة المرتّبة النهائية.

def counting_sort(arr, max_value):
    counts = [0] * (max_value + 1)
    for num in arr:
        counts[num] += 1

    # مجموع تراكمي: counts[i] يصبح "كم عنصرًا <= i"
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]

    output = [0] * len(arr)
    # نمرّ من النهاية للحفاظ على الاستقرار (stability)
    for num in reversed(arr):
        counts[num] -= 1
        output[counts[num]] = num

    return output


print(counting_sort([4, 2, 2, 8, 3, 3, 1], max_value=8))
# [1, 2, 2, 3, 3, 4, 8]

التعقيد: O(n + k) زمنًا ومكانًا، حيث n عدد العناصر وk مدى القيم (أكبر قيمة ممكنة). هذا أسرع من O(n log n) فقط عندما يكون k بحدود معقولة مقارنة بـ n — لو k ضخم جدًا (مثلًا أعداد عشوائية حتى المليار)، تصبح O(n + k) أبطأ وأكثر استهلاكًا للذاكرة بكثير من الخيارات المقارِنة.

💡 المرور على المصفوفة الأصلية بالعكس (reversed(arr)) عند بناء output تفصيلة ضرورية للحفاظ على الاستقرار (عنصران متساويان يحافظان على ترتيبهما النسبي الأصلي) — مهمّة جدًا لأن Radix Sort بالأسفل يعتمد على هذه الخاصية بالذات.

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

Counting Sort ممتازة، لكنها غير عملية إن كان مدى القيم k ضخمًا (أرقام كبيرة). Radix Sort تحلّ هذا: بدل الترتيب حسب القيمة كاملة، ترتّب رقمًا (Digit) واحدًا في كل مرة — من الأقل أهمية (خانة الآحاد) إلى الأكثر أهمية — باستخدام خوارزمية ترتيب مستقرّة (عادة Counting Sort) كخطوة فرعية بكل مرور.

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  # كل رقم من 0 إلى 9

    for num in arr:
        digit = (num // place) % 10
        counts[digit] += 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]

لماذا يجب أن تكون خوارزمية كل مرور مستقرّة؟ لأن ترتيب خانة الآحاد (المرور الأول) يجب أن يبقى محفوظًا نسبيًا عندما نرتّب لاحقًا حسب خانة العشرات، ثم المئات — لو لم يكن المرور الفرعي مستقرًا، كل مرور لاحق قد يُفسد الترتيب الذي أنجزته المرورات السابقة.

التعقيد: O(d × (n + k))، حيث d عدد الخانات (الأرقام) في أكبر قيمة، وk قاعدة العدّ (عادة 10 للأعداد العشرية). لأعداد بعدد خانات ثابت وصغير (مثل معرّفات أو تواريخ)، هذا عمليًا O(n).

متى تستخدم كلًّا منها

التطبيقات الحقيقية

• ترتيب سجلات ضخمة بمفتاح عددي محدود المدى (درجات طلاب، أعمار، تقييمات 1-5).
• خطوة فرعية في بناء مصفوفات اللاحقة (Suffix Arrays) لمعالجة النصوص.
• ترتيب مفاتيح ذات عدد خانات ثابت مثل تواريخ أو معرّفات رقمية طويلة.

أخطاء شائعة

• استخدام Counting Sort مع مدى قيم (k) ضخم جدًا مقارنة بعدد العناصر (n) — يستهلك ذاكرة ووقتًا أكبر بكثير من Merge/Quick Sort بلا أي فائدة.
• استخدام خوارزمية غير مستقرّة كخطوة فرعية داخل Radix Sort — يكسر الترتيب الذي حقّقته المرورات على الخانات الأقل أهمية.
• الظن أن Radix Sort يعمل مباشرة على أي نوع بيانات — يحتاج مفهومًا واضحًا لـ"الخانة" (Digit)، وهو طبيعي للأعداد الصحيحة والنصوص ذات الطول الثابت، لكنه يحتاج تكييفًا لأنواع أخرى.

🎯 التالي: الخلاصة الشاملة لمسار هياكل البيانات والخوارزميات.