الإعلام الآلي — خوارزميات الترتيب: الفقاعي والإدراج والدمج (مقارنة وتعقيد زمني) — الثالثة ثانوي — بكالوريا — المنهاج الجزائري

الخوارزميات: خوارزميات الترتيب (الفقاعي والإدراج والدمج)

خوارزميات الترتيب هي إجراءات تستخدم لترتيب عناصر مجموعة (أعداد، حروف، نصوص) بترتيب معين (تصاعدي أو تنازلي). تعتبر من أهم الخوارزميات في علم الحاسوب ولها تطبيقات واسعة.

1. خوارزمية الترتيب الفقاعي (Bubble Sort)

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

مثال: لترتيب [5, 3, 8, 1] تصاعدياً:
• (5,3) → 3,5,8,1
• (5,8) → 3,5,8,1
• (8,1) → 3,5,1,8 (نهاية المرور 1)
• نكرر حتى الوصول إلى [1,3,5,8]

التعقيد: O(n²) في أسوأ حالة، O(n) في أفضل حالة.

2. خوارزمية الترتيب بالإدراج (Insertion Sort)

مبدأها: بناء المصفوفة المرتبة عنصراً عنصراً بإدراج كل عنصر جديد في موضعه الصحيح في الجزء المرتب.

مثال: لترتيب [5, 3, 8, 1]:
• نبدأ بـ [5]• ندخل 3 → [3,5]• ندخل 8 → [3,5,8]• ندخل 1 → [1,3,5,8]

التعقيد: O(n²) في أسوأ حالة، O(n) في أفضل حالة (مصفوفة مرتبة).

3. خوارزمية الترتيب بالدمج (Merge Sort)

مبدأها: تقسيم المصفوفة إلى نصفين، ترتيب كل نصف بطريقة الدمج (استدعاء ذاتي)، ثم دمج النصفين المرتبين.

التعقيد: O(n log n) في جميع الحالات.

هذه الخوارزمية أسرع من الفقاعي والإدراج للمصفوفات الكبيرة لأنها تستخدم منهج “فرق تسد” (Divide and Conquer).

4. مقارنة بين خوارزميات الترتيب

الترتيب الفقاعي: سهل الفهم لكنه بطيء في المصفوفات الكبيرة.
الترتيب بالإدراج: جيد للمصفوفات الصغيرة أو شبه المرتبة.
الترتيب بالدمج: سريع لكنه يستهلك ذاكرة إضافية.

5. تمارين مقترحة

التمرين 1: طبّق خوارزمية الترتيب الفقاعي على المصفوفة [9, 2, 7, 1, 6] خطوة بخطوة.
التمرين 2: اشرح لماذا التعقيد الزمني لخوارزمية الدمج هو O(n log n).
التمرين 3: اكتب كوداً بلغة بايثون لتنفيذ خوارزمية الترتيب بالإدراج.

للمزيد من المعلومات حول هذا الموضوع، يمكنكم الاطلاع على دروس مشابهة: الحلقات في بايثون و البكتيريا والفطريات.