الدرس 18 · الوحدة 8: اختيار خوارزمية للحل
مقارنة خوارزميات الترتيب
سباق بين خمس خوارزميات على البيانات نفسها: من يفوز، ومتى؟ ⏱ نحو 35 دقيقة.
بعد هذا الدرس ستستطيع أن:
- تشرح الترتيب الفقاعي والاختيار والإدراج وتنفذها.
- تقارن عدد عملياتها على مدخلات عشوائية ومرتبة وشبه مرتبة.
- تختار خوارزمية الترتيب المناسبة من جدول التعقيد.
- تشرح الثبات وترتّب بمعيارين بـ
key.
١ثلاث خوارزميات بسيطة O(n²)
قبل الدمج والسريع، هذه الخوارزميات البسيطة. شغّل كل محاكاة على القائمة نفسها، وقارن عدّادات المقارنات والتبديلات في آخرها:
🎬 محاكاة: الترتيب الفقاعي
مقارنةتبديل أو نقلالمحور أو الوسطفي مكانه النهائي أو وُجد
🎬 محاكاة: الترتيب بالاختيار
مقارنةتبديل أو نقلالمحور أو الوسطفي مكانه النهائي أو وُجد
🎬 محاكاة: الترتيب بالإدراج
مقارنةتبديل أو نقلالمحور أو الوسطفي مكانه النهائي أو وُجد
٢الكود
def bubble_sort(a): a = list(a) n = len(a) for i in range(n - 1): swapped = False for j in range(n - 1 - i): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] swapped = True if not swapped: # لا تبديل: القائمة مرتبة، نتوقف مبكرًا break return a def selection_sort(a): a = list(a) for i in range(len(a) - 1): m = i for j in range(i + 1, len(a)): if a[j] < a[m]: m = j a[i], a[m] = a[m], a[i] return a def insertion_sort(a): a = list(a) for i in range(1, len(a)): key, j = a[i], i - 1 while j >= 0 and a[j] > key: a[j + 1] = a[j] j -= 1 a[j + 1] = key return a data = [29, 10, 14, 37, 13, 5, 33, 21]print(bubble_sort(data))print(selection_sort(data))print(insertion_sort(data))
>>> %Run main.py
[5, 10, 13, 14, 21, 29, 33, 37]
[5, 10, 13, 14, 21, 29, 33, 37]
[5, 10, 13, 14, 21, 29, 33, 37]
>>>
٣سباق على بيانات أكبر
نعدّ المقارنات لكل خوارزمية على ثلاثة أنواع من المدخلات بحجم 500:
import randomrandom.seed(5) def count_bubble(a): a = list(a); c = 0 for i in range(len(a) - 1): sw = False for j in range(len(a) - 1 - i): c += 1 if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j]; sw = True if not sw: break return c def count_selection(a): a = list(a); c = 0 for i in range(len(a) - 1): m = i for j in range(i + 1, len(a)): c += 1 if a[j] < a[m]: m = j a[i], a[m] = a[m], a[i] return c def count_insertion(a): a = list(a); c = 0 for i in range(1, len(a)): key, j = a[i], i - 1 while j >= 0: c += 1 if a[j] <= key: break a[j + 1] = a[j]; j -= 1 a[j + 1] = key return c def count_merge(a): c = 0 def ms(a): nonlocal c if len(a) <= 1: return a m = len(a) // 2; L, R = ms(a[:m]), ms(a[m:]); out = []; i = j = 0 while i < len(L) and j < len(R): c += 1 if L[i] <= R[j]: out.append(L[i]); i += 1 else: out.append(R[j]); j += 1 return out + L[i:] + R[j:] ms(list(a)); return c rnd = random.sample(range(10000), 500)cases = {"عشوائية": rnd, "مرتبة": sorted(rnd), "شبه مرتبة": sorted(rnd)[:490] + rnd[:10]}print(f"{'':10}{'فقاعي':>9}{'اختيار':>9}{'إدراج':>9}{'دمج':>8}")for name, d in cases.items(): print(f"{name:10}{count_bubble(d):>9}{count_selection(d):>9}{count_insertion(d):>9}{count_merge(d):>8}")
>>> %Run main.py
فقاعي اختيار إدراج دمج
عشوائية 123930 124750 61422 3867
مرتبة 499 124750 499 2216
شبه مرتبة 124315 124750 3333 2268
>>>
٤جدول المقارنة
| الخوارزمية | الأفضل | المتوسط | الأسوأ | ذاكرة إضافية | ثابتة؟ | متى تستخدم؟ |
|---|---|---|---|---|---|---|
| الفقاعي | O(n) | O(n²) | O(n²) | O(1) | نعم | للتعليم فقط |
| الاختيار | O(n²) | O(n²) | O(n²) | O(1) | لا | حين يكون التبديل مكلفًا جدًّا (أقل عدد تبديلات) |
| الإدراج | O(n) | O(n²) | O(n²) | O(1) | نعم | القوائم الصغيرة وشبه المرتبة |
| الدمج | O(n log n) | O(n log n) | O(n log n) | O(n) | نعم | ضمان الأداء، والبيانات الكبيرة جدًّا |
| السريع | O(n log n) | O(n log n) | O(n²) | O(log n) | لا | الأسرع عمليًّا غالبًا |
sorted (Timsort) | O(n) | O(n log n) | O(n log n) | O(n) | نعم | دائمًا في بايثون |
٥الثبات والترتيب بمفتاح
الخوارزمية الثابتة Stable تُبقي العناصر المتساوية بترتيبها الأصلي. وهذا مهم حين نرتب بأكثر من معيار: نرتب الطلاب بالاسم، ثم بالمعدل؛ فيبقى أصحاب المعدل الواحد مرتبين بالاسم:
students = [("سارة", 4.5), ("أحمد", 3.8), ("خالد", 4.5), ("منى", 3.8), ("علي", 4.9)] by_name = sorted(students, key=lambda s: s[0])by_gpa = sorted(by_name, key=lambda s: s[1], reverse=True) # ثابت: الاسم يبقى مرتبًا داخل المعدلfor name, gpa in by_gpa: print(gpa, name)
>>> %Run main.py
4.9 علي
4.5 خالد
4.5 سارة
3.8 أحمد
3.8 منى
>>>
في الواقع لا تكتب خوارزمية ترتيب بنفسك؛ استخدم sorted أو list.sort مع key. لكن فهم الخوارزميات يعلّمك تحليل التعقيد، ويفيدك حين تحتاج تعديلًا خاصًّا.
توقّع وتحقّق
أقل عدد تبديلات:
n − 1 تبديل على الأكثر.الأفضل لقائمة شبه مرتبة:
قريب من
O(n).الخوارزمية التي يبقى أداؤها O(n log n) في كل الحالات:
مضمون.
الترتيب الثابت يعني:
Stable.الخلاصة
- الفقاعي والاختيار والإدراج
O(n²)، والدمج والسريعO(n log n). - الإدراج ممتاز للصغيرة وشبه المرتبة، والاختيار أقل تبديلات.
- الثابت يبقي المتساويين بترتيبهما، و
sortedثابت. - في الواقع:
sortedمعkey، ومفتاحtupleلأكثر من معيار.
تحدٍّ برمجي: ترتيب بمعيارين
متوسطرتّب المنتجات: الأقل سعرًا أولًا، وعند تساوي السعر الأكثر تقييمًا أولًا، باستخدام sorted ومفتاح واحد.
المطلوب:
- المفتاح tuple: (السعر، سالب التقييم).
- اطبع كل منتج في سطر: الاسم ثم السعر ثم التقييم.
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
products = [("قهوة", 35, 4.2), ("شاي", 18, 4.8), ("عسل", 60, 4.9), ("هيل", 18, 4.1), ("تمر", 35, 4.7)]شاي 18 4.8
هيل 18 4.1
تمر 35 4.7
قهوة 35 4.2
عسل 60 4.9
💡 تلميح 1
key=lambda p: (p[1], -p[2])💡 تلميح 2
السالب يعكس الترتيب للتقييم وحده.
حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
products = [("قهوة", 35, 4.2), ("شاي", 18, 4.8), ("عسل", 60, 4.9), ("هيل", 18, 4.1), ("تمر", 35, 4.7)] for name, price, rating in sorted(products, key=lambda p: (p[1], -p[2])): print(name, price, rating)