الفرز السريع

يختار قيمة واحدة تُسمّى المحور، وينقل القيم الأصغر إلى يسارها والأكبر إلى يمينها. ثم يكرر الشيء نفسه مع كل جانب.

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

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

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