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