خوارزميات الفرز: Bubble Sort و Selection Sort و Insertion Sort – الثالثة ثانوي (بكالوريا) إعلام آلي – شعبة تقني رياضي

خوارزميات الفرز: Bubble Sort و Selection Sort و Insertion Sort

الثالثة ثانوي (بكالوريا) إعلام آلي – شعبة تقني رياضي – المنهاج الجزائري

1. مفهوم الفرز

الفرز (Sorting) هو عملية ترتيب عناصر مصفوفة (Array) وفق ترتيب معين:

• تصاعدي (Ascending): من الأصغر إلى الأكبر (1, 2, 3, …)
• تنازلي (Descending): من الأكبر إلى الأصغر (…, 3, 2, 1)

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

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

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

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

1. نمرر على المصفوفة من أول عنصر إلى آخر عنصر.
2. نقارن كل عنصرين متجاورين (T[i] و T[i+1]).
3. إذا كان T[i] > T[i+1] (للترتيب التصاعدي)، نقوم بمبادلتهما.
4. بعد كل تمريرة، ينتقل أكبر عنصر إلى نهاية المصفوفة.
5. نكرر العملية مع تجاهل العناصر المرتبة في النهاية.

مثال خطوة بخطوة:

المصفوفة الأولية: [5, 3, 8, 1]

التمريرة	المقارنة	الإجراء	المصفوفة
1	5 > 3	مبادلة	[3, 5, 8, 1]
1	5 < 8	لا شيء	[3, 5, 8, 1]
1	8 > 1	مبادلة	[3, 5, 1, 8]
2	3 < 5	لا شيء	[3, 5, 1, 8]
2	5 > 1	مبادلة	[3, 1, 5, 8]
3	3 > 1	مبادلة	[1, 3, 5, 8]

شيفرة C++ لخوارزمية Bubble Sort:

void bubbleSort(int T[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (T[j] > T[j + 1]) {
                int temp = T[j];
                T[j] = T[j + 1];
                T[j + 1] = temp;
            }
        }
    }
}

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

3. خوارزمية الفرز بالاختيار (Selection Sort)

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

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

1. نبحث عن أصغر عنصر في المصفوفة.
2. نبادله مع العنصر الأول.
3. نبحث عن أصغر عنصر في باقي المصفوفة (بدءاً من العنصر الثاني).
4. نبادله مع العنصر الثاني.
5. نكرر العملية حتى نصل إلى آخر عنصر.

مثال خطوة بخطوة:

المصفوفة الأولية: [5, 3, 8, 1]

التمريرة	البحث عن	التبديل	المصفوفة
1	أصغر = 1 (الموضع 3)	T[0] ↔ T[3]	[1, 3, 8, 5]
2	أصغر = 3 (الموضع 1)	نفسه	[1, 3, 8, 5]
3	أصغر = 5 (الموضع 3)	T[2] ↔ T[3]	[1, 3, 5, 8]

شيفرة C++ لخوارزمية Selection Sort:

void selectionSort(int T[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_indice = i;
        for (int j = i + 1; j < n; j++) {
            if (T[j] < T[min_indice]) {
                min_indice = j;
            }
        }
        if (min_indice != i) {
            int temp = T[i];
            T[i] = T[min_indice];
            T[min_indice] = temp;
        }
    }
}

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

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

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

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

1. نبدأ بالعنصر الثاني (نعتبر العنصر الأول مرتباً).
2. نأخذ العنصر الحالي ونقارنه بالعناصر السابقة (المرتبة).
3. نزيح العناصر الأكبر منه إلى اليمين.
4. ندرج العنصر الحالي في المكان المناسب.
5. ننتقل إلى العنصر التالي ونكرر.

مثال خطوة بخطوة:

المصفوفة الأولية: [5, 3, 8, 1]

العنصر	المقارنة	الإجراء	المصفوفة
3 (i=1)	3 < 5	إزاحة 5 لليمين، إدراج 3	[3, 5, 8, 1]
8 (i=2)	8 > 5	يبقى مكانه	[3, 5, 8, 1]
1 (i=3)	1 < 8, 1 < 5, 1 < 3	إزاحة 8,5,3 لليمين، إدراج 1	[1, 3, 5, 8]

شيفرة C++ لخوارزمية Insertion Sort:

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

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

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

الخاصية	Bubble Sort	Selection Sort	Insertion Sort
عدد المقارنات	n(n−1)/2	n(n−1)/2	≈ n²/4 (وسطياً)
عدد المبادلات (وسطي)	n²/2	n	n²/4 (إزاحات)
التعقيد (أسوأ حالة)	O(n²)	O(n²)	O(n²)
التعقيد (أفضل حالة)	O(n)	O(n²)	O(n)
الاستقرارية	مستقر	غير مستقر	مستقر
سهولة التنفيذ	سهل جداً	سهل	سهل

6. تمارين بكالوريا محلولة

تمرين 1:

طبق خوارزمية Bubble Sort على المصفوفة [9, 2, 5, 1, 7] خطوة بخطوة.

الحل: (بعد حذف التفاصيل الطويلة – النتيجة النهائية: [1, 2, 5, 7, 9])

تمرين 2:

أكمل كتابة الدالة التالية التي تقوم بفرز مصفوفة T ذات n عنصر باستخدام Selection Sort:

void tri(int T[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) {
            /* أكمل الشرط */  __________
        }
        /* أكمل المبادلة */  __________
    }
}

الحل: الشرط: if (T[j] < T[min]) min = j; — المبادلة: if (min != i) { int temp = T[i]; T[i] = T[min]; T[min] = temp; }

7. الخلاصة

• خوارزميات الفرز الثلاثة لها تعقيد O(n²) (غير فعّالة للمصفوفات الكبيرة).
• Bubble Sort مناسب للمبتدئين والتعليم.
• Selection Sort يقلل عدد المبادلات.
• Insertion Sort هو الأفضل للمصفوفات الصغيرة أو المرتبة جزئياً.
• للمصفوفات الكبيرة، نستخدم خوارزميات أسرع مثل Quick Sort أو Merge Sort.

بالتوفيق في البكالوريا! 🇩🇿

📍 دروس مشابهة:

• البرمجة في C++ – إعلام آلي
• الخوارزميات المتقدمة – إعلام آلي