🧩 فهم خوارزمية الترتيب بالإدراج (Insertion Sort) في بايثون

اليوم سنغوص في عالم خوارزميات الترتيب مع واحدة من أبسطها وأكثرها بديهية: خوارزمية الترتيب بالإدراج. إذا كنت تتساءل كيف يمكن لبرنامجك ترتيب قائمة من الأرقام العشوائية من الأصغر إلى الأكبر، فأنت في المكان الصحيح! 🎯

💡 ما هي فكرة خوارزمية Insertion Sort؟

تتشابه فكرة هذه الخوارزمية كثيراً مع الطريقة التي نرتب بها أوراق اللعب في أيدينا. تخيل أنك تحمل مجموعة من الأوراق غير المرتبة. تبدأ بيدك اليسرى فارغة واليمنى تحمل الأوراق. ثم تأخذ ورقة واحدة تلو الأخرى من يدك اليمنى وتضعها في المكان الصحيح في يدك اليسرى، بحيث تظل الأوراق في يدك اليسرى مرتبة طوال الوقت.

هذا بالضبط ما تفعله خوارزمية الإدراج! فهي تقسم المصفوفة إلى قسمين:

  • قسم مرتب: يبدأ بالعنصر الأول فقط ويعتبر مرتباً (مثل يدك اليسرى).
  • قسم غير مرتب: باقي العناصر التي لم يتم ترتيبها بعد (مثل يدك اليمنى).

ثم تأخذ الخوارزمية عنصراً واحداً من القسم غير المرتب وتدرجه في موضعه الصحيح داخل القسم المرتب.

🧠 كيف تعمل الخوارزمية خطوة بخطوة؟

لنفترض أن لدينا مصفوفة صغيرة تحتوي على الأرقام: [5, 2, 4, 6, 1, 3]. سنرتبها تصاعدياً (من الأصغر إلى الأكبر).

  1. البداية: العنصر الأول (5) يعتبر القسم المرتب الوحيد. باقي الأرقام ([2, 4, 6, 1, 3]) هي القسم غير المرتب.
    • الحالة: [5, | 2, 4, 6, 1, 3] (الشريط | يفصل بين القسمين)
  2. التكرار الأول: نأخذ أول عنصر من القسم غير المرتب، وهو الرقم 2. نقارنه بالعناصر في القسم المرتب (5) من اليمين إلى اليسار.
    • 2 < 5، إذن ننقل 5 خطوة لليمين: [5, 5, | 4, 6, 1, 3].
    • لم يعد هناك عناصر للمقارنة، فنضع 2 في الموضع الأول: [2, 5, | 4, 6, 1, 3].
    • أصبح القسم المرتب الآن [2, 5].
  3. التكرار الثاني: نأخذ العنصر التالي (4) من القسم غير المرتب.
    • نقارن 4 مع العناصر في القسم المرتب (من اليمين إلى اليسار).
    • 4 < 5، ننقل 5 لليمين: [2, 5, 5, | 6, 1, 3].
    • 4 > 2، نتوقف. نضع 4 في الموضع قبل 5: [2, 4, 5, | 6, 1, 3].
  4. تستمر هذه العملية مع بقية العناصر (6, 1, 3) حتى يتم ترتيب المصفوفة بالكامل لتصبح [1, 2, 3, 4, 5, 6].

👨‍💻 تنفيذ خوارزمية Insertion Sort في كود بايثون

لنترجم الآن هذه الخطوات إلى كود برمجي واضح وسهل المتابعة.

# تعريف دالة الترتيب بالإدراج
def insertion_sort(arr):
    # نبدأ من العنصر الثاني (المؤشر 1) لأن العنصر الأول يعتبر مرتباً مبدئياً
    for i in range(1, len(arr)):
        # المفتاح هو العنصر الذي نريد إدراجه في المكان الصحيح
        key = arr[i]
        # j يمثل المؤشر الذي سنقارن عنده، يبدأ من العنصر الذي يسبق i مباشرة
        j = i - 1

        # ننقل العناصر الأكبر من المفتاح خطوة واحدة إلى اليمين
        # نستمر طالما j >= 0 والعنصر الحالي في القسم المرتب أكبر من المفتاح
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # انقل العنصر الكبير لليمين
            j -= 1  # تحرك مؤشر j لليسار للمقارنة مع العنصر السابق

        # بعد إيجاد الموضع الصحيح (حيث العنصر السابق أصغر أو يساوي المفتاح)
        # نضع المفتاح في موضعه الجديد
        arr[j + 1] = key

    # الدالة لا ترجع قيمة جديدة، بل تعدل المصفوفة الأصلية (In-place)
    return arr

# مثال لاختبار الدالة
my_list = [5, 2, 4, 6, 1, 3]
print("المصفوفة الأصلية:", my_list)

# استدعاء الدالة لترتيب المصفوفة
sorted_list = insertion_sort(my_list)
print("المصفوفة بعد الترتيب:", sorted_list)

مخرجات الكود:

المصفوفة الأصلية: [5, 2, 4, 6, 1, 3]
المصفوفة بعد الترتيب: [1, 2, 3, 4, 5, 6]

⏱️ تحليل أداء الخوارزمية (باختصار)

  • تعقيد الوقت في أسوأ حالة (Worst-Case): O(n²) - يحدث هذا عندما تكون المصفوفة مرتبة تنازلياً، مما يجبر الخوارزمية على مقارنة وإزاحة كل عنصر.
  • تعقيد الوقت في أفضل حالة (Best-Case): O(n) - يحدث هذا عندما تكون المصفوفة مرتبة أصلاً، فتكتفي الخوارزمية بمقارنة كل عنصر مع سابقه فقط.
  • تعقيد المكان (Space Complexity): O(1) - لأن الخوارزمية ترتب العناصر في نفس المصفوفة دون الحاجة لاستخدام مساحة إضافية كبيرة.

متى نستخدمها؟ تعد Insertion Sort فعالة للغاية عندما تكون المصفوفة صغيرة الحجم أو شبه مرتبة بالفعل.

🧪 جربها بنفسك!

نشجعك على نسخ الكود أعلاه وتجربته في بيئة Python الخاصة بك. حاول تغيير الأرقام في المصفوفة my_list لترى كيف تعمل الخوارزمية مع مجموعات بيانات مختلفة.