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

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

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

مبدأ الخوارزمية

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

خطوات الخوارزمية

1. نبدأ من العنصر الثاني (i = 1)
2. نخزن قيمة العنصر الحالي في متغير مؤقت (key)
3. نقارن key مع العناصر السابقة (j = i-1, i-2, …)
4. إذا كان العنصر السابق أكبر من key، نزيحه إلى اليمين
5. نكرر الخطوة 4 حتى نجد المكان المناسب
6. ندرج key في مكانه المناسب
7. ننتقل إلى العنصر التالي (i++) ونكرر

تطبيق الخوارزمية بلغة C

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

تحليل التعقيد

• أفضل حالة: O(n) عندما تكون المصفوفة مرتبة بالفعل
• أسوأ حالة: O(n²) عندما تكون المصفوفة مرتبة تنازلياً
• الحالة المتوسطة: O(n²)
• الذاكرة الإضافية: O(1) (خوارزمية موضعية)

مثال تطبيقي

تمارين

1. طبق خوارزمية الفرز بالإدراج على المصفوفة [8, 3, 5, 1, 9, 2] خطوة بخطوة.
2. أكتب برنامجاً بلغة C يقرأ 5 أعداد من المستخدم ويرتبها ترتيباً تصاعدياً باستخدام Insertion Sort.
3. قارن بين خوارزمية الفرز بالإدراج وخوارزمية الترتيب بالإدراج من حيث السرعة.
4. ما فائدة كون الخوارزمية موضعية (In-place) من حيث استهلاك الذاكرة؟

للمزيد من المعلومات، راجع درس الخوارزميات: الترتيب بالإدراج ودرس الخوارزميات: البحث الثنائي.

📍 دروس مشابهة

• الإعلام الآلي — قواعد البيانات: لغة SQL – الاستعلامات الأساسية — السنة الثانية ثانوي — المنهاج الجزائري
• الإعلام الآلي — البرمجة بلغة بايثون: التعامل مع الملفات — السنة الثالثة ثانوي — المنهاج الجزائري