خوارزميات الترتيب Selection Sort دليلك الشامل

دليل شامل لإتقان خوارزميات الترتيب (Sorting Algorithms) بلغة بايثون. شرح مبسط وعميق لخوارزميات Selection، Bubble، Insertion، Merge، و Quick Sort، مع تحليل التعقيد الزمني (Big O) وتطبيقات عملية من واقع هندسة البرمجيات.

أهداف التعلم

• شرح آلية عمل خوارزميات الترتيب الخمسة الشهيرة (Bubble, Selection, Insertion, Merge, Quick).
• تنفيذ خوارزمية Selection Sort وفهم علاقتها بالمصفوفات (Arrays) والقوائم المرتبطة (Linked Lists).
• التمييز بين الخوارزميات البسيطة والخوارزميات الفعالة .
• اختيار الخوارزمية الأنسب بناءً على حجم البيانات وسياق المشكلة.

خارطة الطريق

أين كنا؟ تعلمنا في الفصول السابقة أساسيات Big O Notation وكيفية عمل الذاكرة (Memory) والفرق بين Arrays و Linked Lists.

أين نحن؟ نحن الآن في قلب العمليات الخوارزمية. كيف نستخدم ما تعلمناه لترتيب البيانات؟

إلى أين نتجه؟ الفهم العميق للترتيب سيمهد الطريق لفهم "العودية" (Recursion) واستراتيجية "فرق تسد" (Divide and Conquer) في الدروس القادمة.

المتطلبات المسبقة

• معرفة أساسية بلغة Python.
• فهم مبدأ Big O Notation.
• استيعاب مفهوم المصفوفات (Arrays) وكيفية الوصول للعناصر عبر الـ Index.

تمهيد

تخيل أنك تعمل في متجر إلكتروني ضخم (مثل Amazon)، وطلب منك المدير ميزة بسيطة: "أريد زرّاً يرتب المنتجات من الأرخص إلى الأغلى".

يبدو طلباً بسيطاً، أليس كذلك؟

ولكن، إذا كان لديك 10 منتجات، يمكنك ترتيبها يدوياً في ثوانٍ. ماذا لو كان لديك مليون منتج؟

استخدام الخوارزمية الخاطئة قد يجعل الزبون ينتظر ساعة كاملة ليرى النتائج! بينما الخوارزمية الصحيحة ستفعلها في أجزاء من الثانية. الترتيب ليس مجرد تنظيم؛ إنه عمود فقري لسرعة البحث والأداء في علوم الحاسوب.

الترتيب (Sorting) هو عملية تنظيم البيانات في تسلسل معين (تصاعدي أو تنازلي). المشكلة ليست في "كيف نرتب"، بل في "كم يكلفنا الترتيب؟".

في كتاب Grokking Algorithms، يبدأ المؤلف بـ Selection Sort لأنها جسر ممتاز بين الفهم البشري والتفكير الحاسوبي، رغم أنها ليست الأسرع.

سنقسم الخوارزميات إلى عائلتين:

• العائلة البسيطة (Quadratic): سهلة الفهم، بطيئة مع البيانات الكبيرة (). تشمل: Bubble, Selection, Insertion.
• العائلة السريعة (Log-Linear): أكثر تعقيداً، سريعة جداً (). تشمل: Merge, Quick.

شرح المفهوم

أولاً: Selection Sort

فكرتها بسيطة جداً: ابحث في القائمة كاملة عن "أصغر عنصر"، ضعه في سلة جديدة (أو في بداية القائمة)، ثم كرر العملية لما تبقى.

المميزات: سهلة البرمجة، لا تستهلك ذاكرة إضافية كبيرة.

العيوب: بطيئة جداً. عليك فحص القائمة مرة لكل عنصر.

ثانياً: Bubble Sort

تقوم بمقارنة كل عنصر بجاره، وتبديلهما إذا كان الترتيب خاطئاً. العناصر الكبيرة "تطفو" كالفقاعات إلى النهاية.

الحكم: نادراً ما تستخدم في الواقع لأنها الأبطأ في معظم الحالات.

ثالثاً: Insertion Sort

تعمل مثل ترتيب أوراق اللعب في يدك. تسحب ورقة وتضعها في مكانها الصحيح بين الأوراق التي رتبتها سابقاً.

الحكم: ممتازة للقوائم الصغيرة جداً أو المرتبة جزئياً.

رابعاً: Quick Sort & Merge Sort (السرعة الحقيقية)

تعتمد على مبدأ Divide and Conquer (فرق تسد). بدلاً من معالجة القائمة كتلة واحدة، نقسمها لأجزاء صغيرة، نرتب الأجزاء، ثم نجمعها.

Quick Sort: هو الأكثر شيوعاً في المكتبات القياسية للغات البرمجة.

التمثيل البصري

لنتخيل آلية عمل Selection Sort كما وردت في الكتاب، حيث نبحث عن أصغر رقم لنقله للمقدمة.

graph TD
A[Start List: 5, 3, 6, 2, 10] --> B{Scan for Smallest};
B -- Found 2 --> C[Swap 2 with 5];
C --> D[List: 2 | 3, 6, 5, 10];
D --> E{Scan Remaining: 3, 6, 5, 10};
E -- Found 3 --> F[3 is already first, Keep];
F --> G[List: 2, 3 | 6, 5, 10];
G --> H{Scan Remaining: 6, 5, 10};
H -- Found 5 --> I[Swap 5 with 6];
I --> J[Final Sorted: 2, 3, 5, 6, 10];

التطبيق العملي

سنقوم بكتابة دالة selection_sort لأنها محور الفصل، وسنضيف quick_sort لنرى الفرق في القوة.

أ) Selection Sort Implementation

def find_smallest(arr):
"""
دالة مساعدة لإيجاد مؤشر (index) أصغر عنصر في المصفوفة
"""
smallest = arr[0]       # نفترض أن العنصر الأول هو الأصغر
smallest_index = 0      # نخزن مؤشره

```
for i in range(1, len(arr)):
    if arr[i] < smallest:
        smallest = arr[i]
        smallest_index = i
        
return smallest_index

```

def selection_sort(arr):
"""
الخوارزمية الرئيسية: تقوم بإنشاء مصفوفة جديدة وترتيب العناصر فيها
O(n^2) complexity
"""
new_arr = []
# نحتاج لنسخة من المصفوفة لكي لا نعدل الأصلية أثناء الحذف (اختياري)
copied_arr = list(arr)

```
for i in range(len(copied_arr)):
    # 1. جد أصغر عنصر في القائمة المتبقية
    smallest_index = find_smallest(copied_arr)
    
    # 2. انزعه من القائمة القديمة وأضفه للجديدة
    new_arr.append(copied_arr.pop(smallest_index))
    
return new_arr

```

# التجربة

my_list = [5, 3, 6, 2, 10]
print(f"Original: {my_list}")
print(f"Sorted:   {selection_sort(my_list)}")

ب) Quick Sort Implementation (للمقارنة)

def quick_sort(arr):
"""
خوارزمية الترتيب السريع باستخدام مبدأ (فرق تسد)
O(n log n) average case
"""
# Base case: المصفوفة الفارغة أو التي بها عنصر واحد مرتبة تلقائياً
if len(arr) < 2:
return arr
else:
# Recursive case
pivot = arr[0]  # نختار العنصر المحوري

```
    # عناصر أصغر من المحور
    less = [i for i in arr[1:] if i <= pivot]
    
    # عناصر أكبر من المحور
    greater = [i for i in arr[1:] if i > pivot]
    
    # نجمع النتائج: المرتب الصغير + المحور + المرتب الكبير
    return quick_sort(less) + [pivot] + quick_sort(greater)

```

print(f"Quick Sort: {quick_sort([10, 5, 2, 3])}")

تحليل الكود

تحليل Selection Sort:

• القلب النابض: هو الدالة find_smallest. إنها تمر على القائمة كاملة.
• الحلقة المزدوجة: لاحظ أننا ننادي find_smallest (التي تحتوي حلقة تكرار) داخل حلقة تكرار أخرى في selection_sort.
• الرياضيات: حلقة داخل حلقة تعني . هذا يعني لو تضاعفت البيانات، سيزداد الوقت 4 أضعاف!

تحليل Quick Sort:

• Base Case: التوقف عندما تكون المصفوفة صغيرة. هذا يمنع الدخول في حلقة لا نهائية (Infinite Recursion).
• Pivot: هو السر. تقسيم البيانات إلى "أصغر" و "أكبر" يقلل حجم المشكلة في كل خطوة بشكل لوغاريتمي () بدلاً من خطي.

دراسة حالة

السيناريو: تطبيق لتنظيم مواعيد المرضى في عيادة. البيانات: قائمة تحتوي على أوقات الوصول (Time Stamps). المشكلة: الممرضة تدخل البيانات بشكل عشوائي، والنظام يجب أن يعرضها مرتبة زمنياً.

لماذا Selection Sort سيئة هنا؟ إذا كان لديك في العيادة 1000 مريض، ستقوم الخوارزمية بمليون عملية (1,000,000). النظام سيتجمد.

الحل الأفضل: Insertion Sort قد يكون ممتازاً هنا إذا كانت القائمة مرتبة وتضيف مريضاً واحداً جديداً (لأنه سريع جداً في إضافة عنصر لقائمة مرتبة مسبقاً). أما لترتيب قاعدة البيانات كاملة، نستخدم Quick Sort.

تحدي واقعي

تحدي "Top K":

تخيل أنك مهندس في تويتر (X حالياً). تريد عرض "أكثر 10 وسوم (Hashtags) تداولاً" من بين مليون وسم.

هل تحتاج لترتيب المليون وسم بالكامل؟

Selection Sort: سترتب الجميع لتأخذ أول 10. (إهدار هائل للموارد).

التفكير الهندسي: نحتاج فقط لفرز جزئي. خوارزميات مثل Heap Sort أو تعديل على Selection Sort ليتوقف بعد 10 دورات فقط قد يكون حلاً ذكياً، أو استخدام QuickSelect.

زاويه السوق

في مقابلات العمل لدى شركات (Google, Amazon, Meta..)، نادراً ما يُطلب منك كتابة Bubble Sort إلا إذا سُئلت "ما هي أسوأ طريقة لترتيب البيانات؟".

في الواقع العملي، لغة Python تستخدم خوارزمية تسمى Timsort دالة جاهزة .sort(). هي مزيج عبقري بين Merge Sort و Insertion Sort، مصممة لتكون سريعة جداً مع البيانات الحقيقية التي غالباً ما تحتوي على أجزاء مرتبة بالفعل.

تتبع الكود

لنقم بتتبع خوارزمية Selection Sort يدوياً لنرى كيف تتغير المتغيرات في الذاكرة.

المصفوفة الأولية: [11, 4, 15]

التدريبات

المستوى 1: الملاحظة

لديك القائمة التالية: [3, 0, 2, 5].

اكتب شكل القائمة بعد انتهاء الدورة الثانية تماماً باستخدام خوارزمية Selection Sort.

المستوى 2: التعديل

الكود الذي كتبناه يرتب تصاعدياً (من الصغير للكبير). قم بتعديل دالة find_smallest ودالة selection_sort لترتيب البيانات تنازلياً (من الكبير للصغير).

المستوى 3: التحليل

أنت تكتب كوداً لنظام "رادار سرعة". السيارات تمر بسرعة عالية جداً، ويجب عليك إدراج رقم لوحة كل سيارة مسرعة في قائمة مرتبة فوراً لعرضها على الشاشة. القائمة تكون شبه مرتبة دائماً.

أي خوارزمية تختار ولماذا؟ (Selection Sort أم Insertion Sort؟).

التقييم الذاتي

قيم نفسك بصدق:

• أستطيع شرح فكرة Selection Sort.
• أستطيع كتابة كود Selection Sort بلغة Python دون النظر للمرجع (أو بأخطاء بسيطة).
• أفهم لماذا Quick Sort أسرع في الواقع من Selection Sort رغم بساطة الأخيرة.

ما وراء الكود

مفهوم "الاستقرار" (Stability):

في خوارزميات الترتيب، نقول أن الخوارزمية Stable إذا كانت تحافظ على الترتيب النسبي للعناصر المتساوية.

مثال: لديك قائمة منتجات مرتبة حسب التاريخ، وتريد ترتيبها حسب السعر.

إذا كانت الخوارزمية Stable: المنتجات التي لها نفس السعر ستبقى مرتبة حسب التاريخ (كما كانت).

إذا كانت Unstable: قد يختلط ترتيب التاريخ للمنتجات ذات السعر المتشابه.

Selection Sort تعتبر عادةً Unstable (حسب التنفيذ)، بينما Merge Sort تعتبر Stable.

ملخص الدرس

Selection Sort: بسيطة، ابحث عن الأصغر وضعه في المقدمة. تعقيدها . جيدة لتعلم التفكير الخوارزمي ولكنها بطيئة للإنتاج.

Quick Sort: قوية، تعتمد على "فرق تسد". تعقيدها . هي الخيار الشائع للسرعة.

الترتيب ليس مجرد كود، بل هو مفاضلة (Trade-off) بين السرعة، واستهلاك الذاكرة، واستقرار البيانات.

نصائح احترافية

في بايثون: لا تعد اختراع العجلة. استخدم ()list.sort لترتيب القائمة في مكانها، أو sorted(list) لإنشاء نسخة جديدة مرتبة. بايثون تستخدم Timsort وهي خوارزمية فائقة الكفاءة.

Performance: تجنب استخدام الترتيب داخل الحلقات التكرارية (Loops) قدر الإمكان. رتب مرة واحدة، ثم ابحث كما تشاء.

تمهيد للمشروع

هل تساءلت يوماً عن الفرق الحقيقي في السرعة بين هذه الخوارزميات؟ هل هو فرق "جزء من الثانية" أم فرق "دقائق"؟

في مشروعنا القادم، سنقوم بسباق حقيقي. سنضع Selection Sort في مواجهة الدالة الجاهزة في بايثون، وسنرى من يفوز عندما يكون عدد العناصر 10,000 عنصر!

المشروع المصغر

اسم المشروع: The Great Sorting Race (سباق الترتيب الكبير).

المهمة:

اكتب سكربت بايثون يقوم بما يلي:

• توليد قائمة عشوائية تحتوي على 10,000 رقم (بين 1 و 100,000).
• حساب الوقت المستغرق لترتيبها باستخدام selection_sort.
• حساب الوقت المستغرق لترتيبها باستخدام دالة بايثون الجاهزة .sort().
• طباعة الفرق في الوقت.

الكود المساعد:

import time
import random

# 1. Generate Data

data_size = 10000
random_list = [random.randint(1, 100000) for _ in range(data_size)]

# Copy list to be fair

list_1 = list(random_list)
list_2 = list(random_list)

# 2. Test Selection Sort (Using our function from Part 1)

start_time = time.time()
selection_sort(list_1) # تأكد أن دالة selection_sort معرفة لديك
end_time = time.time()
print(f"Selection Sort Time: {end_time - start_time:.5f} seconds")

# 3. Test Python's Built-in Sort (Timsort)

start_time = time.time()
list_2.sort()
end_time = time.time()
print(f"Python Built-in Sort Time: {end_time - start_time:.5f} seconds")

ستندهش من النتيجة! قد تستغرق خوارزميتنا عدة ثوانٍ، بينما دالة بايثون ستنتهي في أجزاء من الألف من الثانية.

أسئلة المراجعة