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