الفرز بالاختيار
يجد أصغر قيمة متبقية ويبدّلها إلى الخانة التالية. تبديلاته قليلة جدًا، لكن عدد مقارناته هو نفسه دائمًا.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- لا
- نعم
الأفضل: كيف يزداد الوقت مع حجم القائمة n عندما تكون المدخلات هي الأسهل لهذه الخوارزمية.
المتوسط: النمو المعتاد للوقت مع n. في n² إذا تضاعف عدد القيم صار الوقت نحو أربعة أضعاف، أما n log n فينمو أبطأ بكثير.
الأسوأ: نمو الوقت مع أصعب المدخلات. مفيد عندما يجب ألا تنخفض السرعة أبدًا.
الذاكرة: كم يحتاج من ذاكرة إضافية غير القائمة. 1 يعني بضعة متغيرات، و n يعني نسخة من القائمة.
مستقر: تحافظ القيمتان المتساويتان على ترتيبهما الأصلي. يهم هذا عند الفرز حسب حقل واحد من السجل.
بلا ذاكرة إضافية: يرتّب داخل القائمة نفسها، دون قائمة ثانية.
- قيد المقارنة
- قيد النقل
- أصغر قيمة حاليًا
- في مكانه النهائي
جرّب هذا: اختر قائمة معكوسة. يبقى عدد المقارنات نفسه تمامًا كما في أي قائمة أخرى.
كيف يعمل
يبحث في الجزء غير المرتّب عن أصغر قيمة، ثم يبدّلها مع أول قيمة غير مرتّبة، فتستقر قيمة أخرى في مكانها النهائي. وهو يفحص كل القيم المتبقية دائمًا، حتى لو كانت القائمة مرتّبة أصلًا.
متى يكون خيارًا جيدًا
مفيد عندما يكون نقل البيانات مكلفًا وقراءتها رخيصة، لأنه يبدّل مرة واحدة على الأكثر لكل خانة. وفي معظم الحالات الأخرى يكون الفرز بالإدراج خيارًا بسيطًا أفضل.