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