ما معنى Insertion Sort (ترتيب الإدراج)؟ شرح مبسّط بالأمثلة والكود
ترتيب الإدراج (Insertion Sort) هو خوارزمية ترتيب تبني المصفوفة المرتبة عنصراً واحداً في كل مرة: تأخذ كل عنصر جديد وتُدرجه في موضعه الصحيح وسط العناصر التي رتّبتها من قبل، تماماً كما ترتّب أوراق اللعب في يدك واحدة تلو الأخرى. هي من أبسط الخوارزميات فهماً، لكن الأهم من الحفظ هو معرفة متى تستخدمها فعلاً، لأنها ليست الأسرع دائماً لكنها تتفوّق في حالات محددة سنوضحها.
الفكرة الأساسية: قسّم المصفوفة ذهنياً إلى جزأين، جزء «مرتَّب» على اليسار (يبدأ بعنصر واحد فقط) وجزء «غير مرتَّب» على اليمين. في كل خطوة تسحب أول عنصر من الجزء غير المرتَّب وتُزحزح العناصر الأكبر منه خطوة واحدة لليمين حتى تجد مكانه، ثم تُسقطه فيه.
كيف تعمل الخوارزمية خطوة بخطوة
- اعتبر العنصر الأول مرتَّباً بذاته، وابدأ الفحص من العنصر الثاني (نسمّيه «المفتاح» key).
- قارن المفتاح بالعنصر الذي يسبقه. طالما كان السابق أكبر من المفتاح، أزِح السابق خطوة لليمين.
- كرّر الإزاحة للخلف حتى تصل إلى عنصر أصغر من المفتاح أو إلى بداية المصفوفة، ثم ضَع المفتاح في الفراغ الناتج.
- انتقل إلى العنصر التالي في الجزء غير المرتَّب وكرّر حتى ينتهي.
انتبه إلى نقطة يخطئ فيها المبتدئون كثيراً: الخوارزمية لا «تبدّل» العنصرين كل مرة، بل تُزحزح العناصر الأكبر ثم تضع المفتاح مرة واحدة في النهاية. فهم هذا الفرق يجعل الكود أسرع وأوضح.
مثال عملي
لنرتّب المصفوفة [5, 2, 9, 1, 6] تصاعدياً:
- المفتاح
2: أصغر من5، نُزحزح5لليمين ونضع2أولاً ←[2, 5, 9, 1, 6]. - المفتاح
9: أكبر من5، يبقى مكانه ←[2, 5, 9, 1, 6]. - المفتاح
1: أصغر من9و5و2، نُزحزحها كلها ونضع1في البداية ←[1, 2, 5, 9, 6]. - المفتاح
6: أصغر من9فقط، نُزحزح9ونضع6قبله ←[1, 2, 5, 6, 9].
انتهى الترتيب. لاحظ أن العناصر التي كانت في مواضعها الصحيحة (مثل 9 في البداية) لم تتحرك، وهذا سرّ كفاءة الخوارزمية مع البيانات شبه المرتَّبة.
الكود بلغة مقروءة
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # إزاحة العنصر الأكبر لليمين
j -= 1
arr[j + 1] = key # وضع المفتاح في موضعه
return arrنفس المنطق ينطبق تقريباً حرفياً في JavaScript وJava وC++، لأنه يعتمد على حلقتين متداخلتين لا على أي بنية بيانات خاصة.
التعقيد الزمني والذاكرة
| المقياس | القيمة |
|---|---|
| أفضل حالة (مصفوفة مرتّبة) | O(n) |
| الحالة المتوسطة | O(n²) |
| أسوأ حالة (مصفوفة معكوسة) | O(n²) |
| الذاكرة الإضافية | O(1) (ترتيب في المكان) |
| مستقرة؟ | نعم |
الميزة الجوهرية أنها تكيّفية (adaptive): كلما اقتربت البيانات من كونها مرتّبة، اقترب أداؤها من الخط المستقيم O(n)، وهو ما لا تمنحه لك خوارزميات مثل الترتيب بالاختيار.
متى تختار Insertion Sort ومتى تتجنّبها
استخدمها عندما تكون البيانات صغيرة (عشرات العناصر) أو شبه مرتّبة أصلاً، أو عندما تصل العناصر تدريجياً (online) وتحتاج إبقاء القائمة مرتّبة لحظياً. تجنّبها مع البيانات الكبيرة العشوائية، فالتعقيد التربيعي يجعلها بطيئة جداً مقارنة بـ Merge Sort أو Quick Sort.
مفارقة يجهلها كثيرون: خوارزميات الترتيب الحديثة في المكتبات القياسية (مثل Timsort في بايثون وجافا) تستدعي داخلياً ترتيب الإدراج للأجزاء الصغيرة، لأنه أسرع فعلياً من التقسيم العودي عند القِطع القصيرة. فهي ليست مجرد أداة تعليمية، بل جزء من محرّكات الترتيب الاحترافية.
مقارنة سريعة بخوارزميات الترتيب الشائعة
| الخوارزمية | متوسط الأداء | مستقرة | في المكان | الأنسب لـ |
|---|---|---|---|---|
| Insertion Sort | O(n²) | نعم | نعم | بيانات صغيرة أو شبه مرتّبة |
| Selection Sort | O(n²) | لا | نعم | تقليل عدد عمليات النقل |
| Bubble Sort | O(n²) | نعم | نعم | التعليم فقط، نادراً عملياً |
| Merge Sort | O(n log n) | نعم | لا | بيانات كبيرة تحتاج استقراراً |
| Quick Sort | O(n log n) | لا | نعم | الأداء العام السريع |
الأسئلة الشائعة
هل ترتيب الإدراج «مستقر»؟ نعم. العناصر المتساوية تحافظ على ترتيبها النسبي الأصلي، لأننا نُزحزح فقط عند وجود عنصر أكبر تماماً من المفتاح، وليس مساوياً له. هذا مهم عند ترتيب سجلات بمفتاحين.
ما الفرق بينه وبين ترتيب الاختيار (Selection Sort)؟ ترتيب الإدراج يبني الجزء المرتَّب بإدراج كل عنصر في مكانه ويستفيد من كون البيانات شبه مرتّبة، بينما ترتيب الاختيار يبحث في كل جولة عن أصغر عنصر متبقٍ ويضعه في مكانه، دون أي استفادة من الترتيب المسبق.
هل يصلح للبيانات الكبيرة جداً؟ لا كخيار أساسي. مع ملايين العناصر العشوائية استخدم O(n log n) مثل Merge أو Quick Sort، واترك ترتيب الإدراج للقِطع الصغيرة أو كطبقة مساعِدة داخل خوارزمية هجينة.
كيف أرتّب تنازلياً بدل تصاعدي؟
اعكس شرط المقارنة فقط: بدّل arr[j] > key إلى arr[j] < key، فيصبح الإدراج من الأكبر إلى الأصغر دون أي تغيير آخر في البنية.