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

مقدمة إلى فرز العد في بايثون

فرز العد هو خوارزمية فرز غير مقارنية تستخدم لتحديد ترتيب العناصر في قائمة معينة. تعتمد هذه الخوارزمية على حساب تكرار كل عنصر في القائمة ثم استخدام هذه المعلومات لإعادة ترتيب العناصر. تُعتبر فرز العد فعّالة بشكل خاص عند التعامل مع مجموعات كبيرة من الأعداد التي تقع ضمن نطاق ضيق من القيم. هذه الخوارزمية تعمل بكفاءة زمنية تبلغ O(n+k) حيث n هو عدد العناصر وk هو مدى القيم.

كيفية تنفيذ فرز العد في بايثون

لتنفيذ فرز العد في بايثون، نبدأ بإنشاء قائمة تُسمى “العداد” حيث يتم تخزين عدد تكرار كل قيمة من القيم الموجودة في القائمة الأصلية. بعد ذلك، نقوم بملء القائمة الأصلية بالقيم بترتيبها الصحيح استناداً إلى معلومات التكرار المخزنة في “العداد”. دعونا نلقي نظرة على مثال توضيحي.

def counting_sort(arr):
    # البحث عن أكبر قيمة في القائمة
    max_val = max(arr)
    
    # إنشاء قائمة العداد بطول أكبر قيمة + 1
    count = [0] * (max_val + 1)
    
    # حساب تكرار كل عنصر
    for num in arr:
        count[num] += 1
    
    # إعادة ترتيب العناصر في القائمة الأصلية
    index = 0
    for i, cnt in enumerate(count):
        while cnt > 0:
            arr[index] = i
            index += 1
            cnt -= 1

# مثال على استخدام فرز العد
arr = [4, 2, 2, 8, 3, 3, 1]
counting_sort(arr)
print("القائمة المرتبة:", arr)

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

أمثلة أخرى على فرز العد

يمكن أن يكون فرز العد مفيدًا في العديد من السياقات، مثل ترتيب درجات الطلاب، أو توزيع الأرباح في الشركات، أو حتى في الألعاب الإلكترونية حيث تحتاج إلى ترتيب النقاط. إليك مثال آخر لتوضيح كيفية استخدام فرز العد في سيناريو مختلف.

def counting_sort_grades(grades):
    # البحث عن أعلى درجة
    max_grade = max(grades)
    
    # إنشاء قائمة العداد بطول أعلى درجة + 1
    count = [0] * (max_grade + 1)
    
    # حساب تكرار كل درجة
    for grade in grades:
        count[grade] += 1
    
    # إعادة ترتيب الدرجات
    index = 0
    for i, cnt in enumerate(count):
        while cnt > 0:
            grades[index] = i
            index += 1
            cnt -= 1

# مثال على استخدام فرز العد مع الدرجات
grades = [88, 75, 90, 85, 85, 92, 75]
counting_sort_grades(grades)
print("الدرجات المرتبة:", grades)

في هذا المثال، نستخدم فرز العد لفرز درجات الطلاب. هذا يعطينا فكرة عن مدى فعالية فرز العد في التعامل مع البيانات التي تحتوي على تكرارات متعددة.