الفرز بالاختيار

يجد أصغر قيمة متبقية ويبدّلها إلى الخانة التالية. تبديلاته قليلة جدًا، لكن عدد مقارناته هو نفسه دائمًا.

• الأفضل Ω(n²)
• المتوسط Θ(n²)
• الأسوأ O(n²)
• الذاكرة O(1)
• غير مستقر
• بلا ذاكرة إضافية

ماذا تعني هذه المصطلحات؟

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