Counting Sort

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

Counting Sort يرتّب بعدّ تكرار كل قيمة بدل مقارنة العناصر، بتعقيد O(n + k) حيث k مدى القيم — أسرع من الترتيب المقارِن لكن فقط عندما k محدود المدى.

خوارزمية ترتيب لامقارِنة (Non-Comparison): تُحصي تكرار كل قيمة، تحوّل العدّ لمجموع تراكمي يمثّل الموضع النهائي، ثم تبني المصفوفة الناتجة بالمرور على المدخل بالعكس للحفاظ على الاستقرار (Stability).

الصياغة

counts = [0] * (max_value + 1)
for num in arr:
    counts[num] += 1
for i in range(1, len(counts)):
    counts[i] += counts[i - 1]

📄 مثال

def counting_sort(arr, max_value):
    counts = [0] * (max_value + 1)
    for num in arr:
        counts[num] += 1
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]
    output = [0] * len(arr)
    for num in reversed(arr):
        counts[num] -= 1
        output[counts[num]] = num
    return output

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

أهم النقاط

النقطة	الوظيفة
التعقيد الزمني والمكاني	O(n + k) — n عدد العناصر، k مدى القيم
مستقرّة (Stable)؟	نعم — شرط أساسي لاستخدامها كخطوة فرعية داخل Radix Sort
الشرط العملي	فعّالة فقط عندما k ليست أكبر بكثير من n، وإلا تستهلك ذاكرة ووقتًا زائدين

💡 نصائح عملية

استخدمها عندما يكون مدى القيم (k) محدودًا ومعروفًا مسبقًا (درجات، أعمار، تقييمات) لا عندما يكون المدى واسعًا أو غير معروف

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

استخدامها مع مدى قيم ضخم مقارنة بعدد العناصر — أبطأ وأكثر استهلاكًا للذاكرة من Merge/Quick Sort بلا أي فائدة حينها

🎓 تريد فهم الصورة الكاملة خطوة بخطوة؟ ابدأ من مسار DSA الكامل بالعربي.