الإعلام الآلي — خوارزميات الترتيب: Insertion Sort و Selection Sort — الثانية ثانوي (شعب علمية) — بكالوريا — المنهاج الجزائري

درس في الإعلام الآلي مخصص لتلاميذ السنة الثانية ثانوي حول خوارزميات الترتيب (الفرز). المحتوى يتبع المنهاج الرسمي الجزائري ويساعد في التحضير للبكالوريا.

المحتوى النظري

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

Selection Sort: نبحث عن أصغر عنصر ونضعه في أول المصفوفة، ثم نكرر.

Insertion Sort: نأخذ عناصر واحدا تلو الآخر وندرجها في الموضع المناسب.

القواعد الأساسية

1. التعقيد الزمني: O(n2) لكل من Insertion و Selection في أسوأ الحالات.

2. Selection Sort: بسيط لكنه بطيء للمصفوفات الكبيرة.

3. Insertion Sort: فعال للمصفوفات الصغيرة أو القريبة من الترتيب.

4. Quick Sort: أسرع خوارزمية (O(n log n)) في المتوسط.

تمارين بكالوريا

تمرين 1:

طبق خوارزمية Selection Sort على المصفوفة [64, 25, 12, 22, 11].

الحل: نبحث عن الأصغر 11 نضعه في البداية: [11, 25, 12, 22, 64]. ثم الأصغر التالي 12: [11, 12, 25, 22, 64]. ثم 22: [11, 12, 22, 25, 64].

تمرين 2 (بكالوريا 2024):

طبق Insertion Sort على [5, 2, 4, 6, 1, 3].

الحل: نبدأ بـ 5. ندخل 2 قبله: [2, 5, 4, 6, 1, 3]. ندخل 4 بين 2 و 5: [2, 4, 5, 6, 1, 3]. ندخل 6: [2, 4, 5, 6, 1, 3]. ندخل 1 في البداية: [1, 2, 4, 5, 6, 3]. ندخل 3: [1, 2, 3, 4, 5, 6].

دروس مشابهة

• الإعلام الآلي — خوارزميات الترتيب: Bubble Sort
• الإعلام الآلي — خوارزميات البحث: البحث الخطي والثنائي