شرح خوارزمية الفرز بالاختيار (Selection Sort) بالأمثلة والكود

الفرز بالاختيار (Selection Sort) هو خوارزمية ترتيب بسيطة تعمل بفكرة واحدة متكررة: في كل جولة تبحث عن أصغر عنصر متبقٍّ في المصفوفة وتضعه في مكانه الصحيح على اليسار، ثم تكرّر العملية على ما تبقّى حتى تُرتَّب القائمة بالكامل. هي من أوائل ما يتعلّمه طالب علوم الحاسوب لأنها سهلة الفهم والتنفيذ، لكنها بطيئة على البيانات الكبيرة لأن تعقيدها الزمني هو O(n²). في هذا الشرح نفكّكها خطوة بخطوة مع كود جاهز ونوضّح متى تستحق الاستخدام فعلاً ومتى الأفضل تجنّبها.

الفكرة الأساسية في جملة واحدة

تخيّل أنك ترتّب أوراقاً مبعثرة تصاعدياً. تمرّ على كل الأوراق لتجد أصغر رقم، تضعه أولاً، ثم تمرّ على الباقي لتجد ثاني أصغر رقم وتضعه ثانياً، وهكذا. الخوارزمية تقسّم القائمة ذهنياً إلى جزأين: جزء مُرتَّب يكبر من اليسار، وجزء غير مرتَّب يصغر من اليمين. في كل خطوة "تختار" أصغر عنصر من الجزء غير المرتَّب وتنقله إلى نهاية الجزء المرتَّب. من هنا جاء الاسم: فرز بالاختيار.

كيف تعمل خطوة بخطوة

لنأخذ المصفوفة: [29, 10, 14, 37, 13] ونرتّبها تصاعدياً.

1. الجولة الأولى: ابحث عن الأصغر بين كل العناصر. الأصغر هو 10. بدّله مع العنصر في الموضع الأول (29). النتيجة: [10, 29, 14, 37, 13].
2. الجولة الثانية: ابحث عن الأصغر بدءاً من الموضع الثاني (29, 14, 37, 13). الأصغر هو 13. بدّله مع 29. النتيجة: [10, 13, 14, 37, 29].
3. الجولة الثالثة: ابحث عن الأصغر بدءاً من الموضع الثالث (14, 37, 29). الأصغر هو 14 وهو أصلاً في مكانه، فلا حاجة للتبديل. النتيجة: [10, 13, 14, 37, 29].
4. الجولة الرابعة: ابحث عن الأصغر بين (37, 29). الأصغر هو 29. بدّله مع 37. النتيجة: [10, 13, 14, 29, 37].

العنصر الأخير يبقى تلقائياً في مكانه، فالقائمة مرتّبة الآن. لاحظ نقطة عملية مهمة: لمصفوفة فيها n عنصراً تحتاج إلى n-1 جولة فقط، لأنك حين ترتّب أول n-1 عنصر يكون الأخير قد استقرّ في مكانه حتماً.

الكود بلغتَي بايثون وجافاسكريبت

هذا تنفيذ واضح بلغة بايثون:

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i               # نفترض أن الأصغر هو العنصر الحالي
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j       # حدّثنا موضع الأصغر
        if min_index != i:          # بدّل فقط عند الحاجة
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

print(selection_sort([29, 10, 14, 37, 13]))  # [10, 13, 14, 29, 37]

ونفس المنطق بلغة جافاسكريبت:

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

نصيحة عملية من التجربة: لا تُجرِ التبديل داخل الحلقة الداخلية كلما وجدت عنصراً أصغر. احفظ موضع الأصغر فقط في متغير، وبدّل مرة واحدة في نهاية كل جولة. هذا يقلّل عدد عمليات التبديل إلى n-1 تبديلاً كحد أقصى، وهي أقل ميزة يتفوّق بها الفرز بالاختيار على غيره كما سنرى.

تحليل التعقيد الزمني والمكاني

بغضّ النظر عن ترتيب البيانات (مرتّبة، عكسية، أو عشوائية) تقوم الخوارزمية دائماً بمقارنة كل عنصر بكل العناصر التي بعده. عدد المقارنات ثابت تقريباً ويساوي n(n-1)/2.

المقياس	القيمة
أفضل حالة	O(n²)
الحالة المتوسطة	O(n²)
أسوأ حالة	O(n²)
الذاكرة الإضافية	O(1) — ترتيب في المكان
عدد عمليات التبديل	O(n) كحد أقصى
مستقرّة (Stable)؟	لا في التنفيذ التقليدي

الملاحظة المهمة هنا أن الفرز بالاختيار لا "يستفيد" من كون البيانات شبه مرتّبة؛ فحتى لو كانت المصفوفة مرتّبة أصلاً سيقوم بكل المقارنات. هذا يميّزه سلباً عن الفرز بالإدراج (Insertion Sort) الذي يقترب من O(n) على البيانات شبه المرتّبة.

الفرز بالاختيار أم الخوارزميات الأخرى؟

الخوارزمية	متوسط التعقيد	الذاكرة	مستقرّة؟	ملاحظة
الفرز بالاختيار	O(n²)	O(1)	لا	أقل عدد تبديلات
الفرز بالإدراج	O(n²)	O(1)	نعم	ممتاز للبيانات شبه المرتّبة
الفرز الفقاعي	O(n²)	O(1)	نعم	الأبطأ عملياً غالباً
الفرز السريع	O(n log n)	O(log n)	لا	الأسرع عملياً في الغالب
الفرز الدمجي	O(n log n)	O(n)	نعم	مضمون وثابت الأداء

الخلاصة العملية: على البيانات الكبيرة استخدم دائماً خوارزمية بتعقيد O(n log n) مثل الفرز السريع أو الدمجي، أو ببساطة الدالة الجاهزة في لغتك (sorted() في بايثون أو .sort() في جافاسكريبت) لأنها مُحسَّنة بعناية. للفرز بالاختيار ميزة واحدة حقيقية: عدد عمليات التبديل قليل جداً (O(n))، ما يجعله مفيداً عندما تكون عملية الكتابة/التبديل نفسها مكلفة، كما في ذاكرة الفلاش محدودة دورات الكتابة.

متى تستخدم الفرز بالاختيار فعلاً؟

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

في أي سياق إنتاجي جادّ خارج هذه الحالات، الأفضل تجنّبه لصالح خوارزمية أسرع.

الأسئلة الشائعة

هل الفرز بالاختيار خوارزمية مستقرّة (Stable)؟ لا، في تنفيذه التقليدي القائم على التبديل قد يغيّر الترتيب النسبي للعناصر المتساوية. يمكن جعله مستقرّاً بتعديله ليُدرج العنصر بدل تبديله، لكن ذلك يزيد التكلفة.

ما الفرق بينه وبين الفرز الفقاعي؟ كلاهما O(n²)، لكن الفرز الفقاعي يبدّل العناصر المتجاورة كثيراً في كل تمريرة، بينما الفرز بالاختيار يبدّل مرة واحدة فقط في كل جولة. لذا يقوم الفرز بالاختيار بعمليات تبديل أقل بكثير رغم تساوي عدد المقارنات.

هل يعمل على الترتيب التنازلي؟ نعم، فقط ابحث عن أكبر عنصر بدل الأصغر في كل جولة (غيّر شرط المقارنة من < إلى >).

هل يستهلك ذاكرة إضافية؟ لا، إنه يرتّب "في المكان" (In-place) ويستخدم ذاكرة إضافية ثابتة O(1) بغضّ النظر عن حجم المدخلات.