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

شرح خوارزمية Counting Sort في بايثون: أبسط مما تتخيل! 🧮

اليوم سنتعرف على خوارزمية فرز رائعة ومميزة تسمى Counting Sort أو "فرز العد". إذا كنت تظن أن الخوارزميات معقدة، فاستعد لتغير رأيك بعد هذا الدرس!

ما هي خوارزمية Counting Sort؟ 🤔

لفهم الفكرة، تخيل أن لديك مجموعة من الكرات بألوان مختلفة (مثلاً: أحمر، أزرق، أخضر) وتريد ترتيبها حسب اللون. إحدى الطرق السهلة هي أن تعد كم كرة من كل لون لديك، ثم تضعها بالترتيب بناءً على هذا العد.

هذا بالضبط ما تفعله Counting Sort! هي خوارزمية فرز لا تقارن العناصر مع بعضها البعض (مثل Bubble Sort أو Quick Sort)، بل تعتمد على عد تكرارات كل قيمة موجودة في المصفوفة الأصلية.

المميزات:

• ⚡ سريعة جداً عندما يكون نطاق البيانات (الفرق بين أصغر وأكبر قيمة) محدوداً وليس كبيراً.
• 🧠 بسيطة الفهم نسبياً.
• ⏳ زمن تنفيذها خطي، أي O(n + k)، حيث n عدد العناصر و k نطاق القيم.

العيوب:

• 💾 غير فعّالة في الذاكرة إذا كان نطاق القيم (k) كبيراً جداً (مثلاً، إذا كنت تفرز أرقاماً بين 1 و 10000).
• 📊 مناسبة فقط للبيانات ذات القيم الصحيحة (أعداد صحيحة) وليست مناسبة للكلمات أو الأعداد العشرية في صورتها الأساسية.

متى نستخدم Counting Sort؟ 🎯

استخدم Counting Sort عندما:

1. تكون البيانات عبارة عن أعداد صحيحة.
2. يكون نطاق هذه الأعداد (k) معروفاً وأصغر بكثير من عدد العناصر (n). مثلاً، فرز درجات الطلاب (من 0 إلى 100) في فصل به 1000 طالب.

خطوات خوارزمية Counting Sort خطوة بخطوة 🚶‍♂️🚶‍♂️🚶‍♂️

لنفرض أن لدينا مصفوفة صغيرة نريد فرزها: [4, 2, 2, 8, 3, 3, 1]

الخطوة 1: أوجد أكبر عنصر (الحد الأقصى) ندور على المصفوفة لايجاد أكبر قيمة. في مثالنا، أكبر قيمة هي 8. سنحتاج هذا الرقم لإنشاء مصفوفة العد.

الخطوة 2: أنشئ مصفوفة للعد (Count Array) ننشئ مصفوفة جديدة بحجم max + 1 (8 + 1 = 9). في البداية، جميع قيمها تكون صفر. count_array = [0, 0, 0, 0, 0, 0, 0, 0, 0] مؤشرات هذه المصفوفة تمثل القيم المحتملة (من 0 إلى 8).

الخطوة 3: عد تكرار كل قيمة ندور على المصفوفة الأصلية ونزيد العداد في الموضع المناسب.

• نرى الرقم 4 -> نزيد قيمة العنصر في الموضع 4 ليصبح 1.
• نرى الرقم 2 -> نزيد قيمة العنصر في الموضع 2 ليصبح 1.
• نرى الرقم 2 مرة أخرى -> نزيد الموضع 2 ليصبح 2.
• ... وهكذا.

في النهاية، تصبح مصفوفة العد لدينا كالتالي: count_array = [0, 1, 2, 2, 1, 0, 0, 0, 1] هذا يعني:

• القيمة 0 تكررت 0 مرة.
• القيمة 1 تكررت 1 مرة.
• القيمة 2 تكررت 2 مرة.
• ... والقيمة 8 تكررت 1 مرة.

الخطوة 4: أنشئ المصفوفة النهائية (المرتبة) الآن، ندور على مصفوفة العد. نبدأ من أصغر قيمة (المؤشر 0) إلى الأكبر (المؤشر 8). نكتب كل قيمة بعدد مرات تكرارها.

• المؤشر 0: العدد 0 -> نكتبه 0 مرة (نتخطاه).
• المؤشر 1: العدد 1 -> نكتبه 1 مرة -> المصفوفة الجديدة: [1]
• المؤشر 2: العدد 2 -> نكتبه 2 مرة -> المصفوفة الجديدة: [1, 2, 2]
• المؤشر 3: العدد 3 -> نكتبه 2 مرة -> المصفوفة الجديدة: [1, 2, 2, 3, 3]
• ... وهكذا حتى المؤشر 8.

ستحصل في النهاية على المصفوفة المرتبة: [1, 2, 2, 3, 3, 4, 8] ✅

تنفيذ كود Counting Sort في بايثون 💻

لنترجم هذه الخطوات إلى كود بايثون واضح وسهل.

def counting_sort(arr):
    """
    دالة لفرز مصفوفة من الأعداد الصحيحة باستخدام خوارزمية فرز العد.
    """
    # الخطوة 1: إيجاد أكبر عنصر في المصفوفة
    max_val = max(arr)
    
    # الخطوة 2: إنشاء مصفوفة العد وتهيئتها بالأصفار
    # حجمها هو max_val + 1 (للتأكد من وجود مكان للقيمة القصوى)
    count_array = [0] * (max_val + 1)
    
    # الخطوة 3: عد تكرار كل قيمة في المصفوفة الأصلية
    for num in arr:
        count_array[num] += 1  # نزيد العداد الخاص بهذه القيمة بواحد
    
    # الخطوة 4: بناء المصفوفة النهائية المرتبة
    sorted_array = []  # مصفوفة جديدة فارغة لوضع النتيجة النهائية
    
    # نمر على كل قيمة (مؤشر) في مصفوفة العد
    for value in range(len(count_array)):
        # count_array[value] تخبرنا بعدد مرات ظهور القيمة (value)
        # نضيف القيمة (value) بعدد مرات ظهورها إلى المصفوفة المرتبة
        sorted_array.extend([value] * count_array[value])
    
    return sorted_array

# مثال لاختبار الدالة
my_list = [4, 2, 2, 8, 3, 3, 1]
print("المصفوفة الأصلية:", my_list)

sorted_list = counting_sort(my_list)
print("المصفوفة بعد الفرز:", sorted_list)

ماذا يحدث في الكود؟

1. نستخدم الدالة max() لايجاد أكبر قيمة.
2. ننشئ count_array كقائمة مليئة بالأصفار.
3. نستخدم حلقة for لعد التكرارات.
4. نستخدم حلقة for أخرى مع الدالة extend() لملء المصفوفة النهائية بناءً على العد.

خلاصة الدرس 📝

تهانينا! لقد تعلمت اليوم:

• مفهوم خوارزمية Counting Sort القائمة على العد.
• مميزاتها وعيوبها وأفضل حالات استخدامها.
• الخطوات المنطقية الأربع للخوارزمية.
• كيفية كتابة كود ينفذ هذه الخوارزمية في بايثون ببساطة.

تذكر أن قوة Counting Sort تكمن في سرعتها عندما يكون نطاق البيانات محدوداً.