الفرز بالكومة

يرتّب القائمة على شكل كومة، أي شجرة يكون فيها كل أب أكبر من أبنائه. ثم ينقل أكبر قيمة إلى النهاية، مرة بعد مرة.

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

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

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