فهم خوارزميات الترتيب: شرح عملي لأشهر أساليب الفرز في البرمجة

مقدمة: لماذا نحتاج إلى فهم خوارزميات الترتيب؟

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

في هذا الدليل، سنستعرض مجموعة من أشهر خوارزميات الترتيب بطريقة مبسطة وعملية، مع التركيز على الفكرة الأساسية لكل خوارزمية، وآلية عملها، والفروق بينها، إضافة إلى توضيح مفهوم التعقيد الزمني مثل O(n^2) وO(n log n). كما أن الأمثلة البرمجية المعروضة تعتمد على لغة C++، لكن المفاهيم نفسها قابلة للتطبيق في لغات مثل Python وJava وC.

ما المقصود بخوارزميات الترتيب؟

خوارزميات الترتيب هي خطوات منظمة لإعادة ترتيب عناصر مصفوفة أو قائمة وفق معيار محدد، وغالباً يكون الترتيب تصاعدياً أو تنازلياً. على سبيل المثال، إذا كانت لدينا المصفوفة [2, 3, 1, 5] فإن الهدف هو تحويلها إلى [1, 2, 3, 5] في حال الترتيب التصاعدي.

تكمن أهمية هذه الخوارزميات في أنها تُستخدم كأساس في عمليات كثيرة، مثل:

• تنظيم البيانات قبل البحث.
• تحسين سرعة بعض العمليات الحسابية والمنطقية.
• معالجة النتائج في التطبيقات المالية والإدارية.
• بناء هياكل بيانات وخوارزميات أكثر تعقيداً.

المتطلبات الأساسية لفهم أمثلة الترتيب

لفهم الأمثلة البرمجية بصورة جيدة، من الأفضل أن تكون لديك معرفة أساسية بـ:

• المصفوفات Arrays.
• الحلقات التكرارية مثل for وwhile.
• الجمل الشرطية if.
• فكرة تبديل القيم باستخدام متغير مؤقت مثل temp.

فكرة التبديل بين عنصرين

كثير من خوارزميات الترتيب تعتمد على مقارنة عنصرين ثم تبديل موقعيهما إذا كان ترتيبهما غير صحيح. ويُنفّذ ذلك غالباً باستخدام متغير وسيط.

int temp = a[i];
a[i] = a[j];
a[j] = temp;

هذا النمط البسيط هو حجر الأساس في أكثر من خوارزمية سنناقشها لاحقاً.

الترتيب البسيط بالمقارنة المباشرة

كيف تعمل الفكرة؟

نبدأ من أول عنصر في المصفوفة، ثم نقارنه بكل العناصر التي تليه. إذا وجدنا عنصراً أصغر منه، نقوم بتبديل القيمتين. مع تكرار هذه العملية على جميع العناصر، تبدأ المصفوفة بالاقتراب تدريجياً من الترتيب الصحيح.

مثلاً، إذا كانت المصفوفة [2, 3, 1, 5]:

1. نقارن 2 مع 3، فلا يحدث تبديل.
2. نقارن 2 مع 1، فنجد أن 1 أصغر، لذا يتم التبديل.
3. نقارن العنصر الحالي مع ما بعده حتى نهاية المصفوفة.

مثال برمجي بلغة C++

#include <iostream>
#include <cstdlib>
using namespace std;

#define MAX 100

int main() {
    int n;
    int array[MAX];

    cin >> n;

    for (int i = 0; i < n; i++) {
        array[i] = rand();
    }

    cout << "Unsorted array:" << endl;
    for (int i = 0; i < n; i++) {
        cout << array[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (array[j] < array[i]) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }

    cout << "Sorted array:" << endl;
    for (int i = 0; i < n; i++) {
        cout << array[i] << " ";
    }
    cout << endl;

    return 0;
}

الترتيب التنازلي

لتحويل الترتيب من تصاعدي إلى تنازلي، يكفي تعديل شرط المقارنة من array[j] < array[i] إلى array[j] > array[i].

خوارزمية الترتيب بالاختيار Selection Sort

فكرة الخوارزمية

تعتمد Selection Sort على تقسيم المصفوفة إلى جزأين:

• جزء مرتب في البداية.
• وجزء غير مرتب نبحث داخله عن أصغر عنصر.

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

خطوات العمل

1. ابدأ من أول فهرس.
2. ابحث عن أصغر عنصر في بقية المصفوفة.
3. بدّل هذا العنصر مع العنصر الموجود في البداية.
4. كرّر العملية مع الفهرس التالي.

مثال برمجي

#include <iostream>
using namespace std;

void swapValues(int a[], int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

int locationOfSmallest(int a[], int s, int e) {
    int i = s;
    int j = i;

    while (i <= e) {
        if (a[i] < a[j]) {
            j = i;
        }
        i++;
    }

    return j;
}

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int j = locationOfSmallest(a, i, n - 1);
        swapValues(a, i, j);
    }
}

void display(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {100, 12, 93, 11, 32, 39, 1, 9, 102};
    int size = sizeof(arr) / sizeof(int);

    display(arr, size);
    selectionSort(arr, size);
    display(arr, size);

    return 0;
}

مميزات وقيود Selection Sort

• سهلة الفهم والتنفيذ.
• مناسبة للتعلم وبناء الأساس المفاهيمي.
• غير فعالة مع مجموعات البيانات الكبيرة.
• تعقيدها الزمني غالباً O(n^2).

خوارزمية الفقاعات Bubble Sort

ما الذي يميزها؟

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

آلية العمل

1. قارن كل عنصر بالعنصر المجاور له.
2. إذا كان العنصر الأول أكبر من الثاني، بدّل بينهما.
3. استمر حتى نهاية المصفوفة.
4. كرّر العملية حتى تصبح المصفوفة مرتبة بالكامل.

مثال برمجي

#include <iostream>
using namespace std;

void swapValues(int a[], int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

void bubbleProcess(int a[], int n) {
    int i = n - 1;
    while (i > 0) {
        if (a[i] < a[i - 1]) {
            swapValues(a, i, i - 1);
        }
        i--;
    }
}

void bubbleSort(int a[], int n) {
    int i = 0;
    while (i < n - 1) {
        bubbleProcess(a, n);
        i++;
    }
}

void display(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {102, 293, 19, 38, 311, 1, 32, 11, 39};
    int size = sizeof(arr) / sizeof(int);

    display(arr, size);
    bubbleSort(arr, size);
    display(arr, size);

    return 0;
}

متى تُستخدم؟

تُعد Bubble Sort من أكثر الخوارزميات التعليمية شهرة، لكنها ليست مناسبة عملياً عند التعامل مع بيانات كبيرة بسبب بطئها النسبي وكون تعقيدها الزمني يصل عادة إلى O(n^2).

خوارزمية الإدراج Insertion Sort

الفكرة الأساسية

تفترض Insertion Sort أن جزءاً من المصفوفة مرتب بالفعل، ثم تأخذ العنصر التالي وتُدرجه في المكان المناسب داخل الجزء المرتب. هذه الفكرة تشبه ترتيب أوراق اللعب في اليد: تلتقط ورقة جديدة ثم تضعها في موقعها الصحيح بين الأوراق السابقة.

كيف تعمل؟

1. اعتبر أن أول عنصر مرتب مبدئياً.
2. خذ العنصر التالي واحفظه في متغير مثل key.
3. حرّك العناصر الأكبر منه خطوة إلى اليمين.
4. ضع key في موقعه المناسب.
5. كرّر العملية حتى نهاية المصفوفة.

مثال برمجي

#include <iostream>
using namespace std;

void insertItem(int a[], int n, int i) {
    int key = a[i];
    int j = i - 1;

    while (j >= 0 && a[j] > key) {
        a[j + 1] = a[j];
        j = j - 1;
    }

    a[j + 1] = key;
}

void insertionSort(int a[], int n) {
    int i = 1;
    while (i < n) {
        insertItem(a, n, i);
        i++;
    }
}

void display(int a[], int n) {
    int i = 0;
    while (i < n) {
        cout << a[i] << " ";
        i++;
    }
    cout << endl;
}

int main() {
    int arr[] = {102, 293, 19, 38, 311, 1, 32, 11, 39};
    int size = sizeof(arr) / sizeof(int);

    display(arr, size);
    insertionSort(arr, size);
    display(arr, size);

    return 0;
}

متى تكون فعالة؟

تُظهر Insertion Sort أداءً جيداً نسبياً عندما تكون البيانات صغيرة أو شبه مرتبة مسبقاً، لكنها مع المصفوفات الكبيرة تبقى أقل كفاءة من الخوارزميات الأسرع مثل Merge Sort.

خوارزمية الدمج Merge Sort

لماذا تُعد أقوى من سابقاتها؟

تُعد Merge Sort من الخوارزميات الفعالة جداً لأنها تعتمد على مبدأ Divide and Conquer، أي تقسيم المشكلة إلى أجزاء أصغر ثم حل كل جزء ودمجه في النهاية.

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

الفكرة ببساطة

1. قسّم المصفوفة إلى نصفين.
2. رتّب كل نصف بشكل مستقل باستخدام الاستدعاء الذاتي Recursion.
3. ادمج النصفين المرتبين في مصفوفة واحدة مرتبة.

مثال برمجي

#include <iostream>
using namespace std;

void combine(int a[], int s, int m, int e) {
    int* buffer = new int[e + 1];

    int k = s;
    while (k <= e) {
        buffer[k] = a[k];
        k = k + 1;
    }

    int i = s;
    int j = m + 1;
    k = s;

    while (i <= m && j <= e) {
        if (buffer[i] <= buffer[j]) {
            a[k] = buffer[i];
            i = i + 1;
        } else {
            a[k] = buffer[j];
            j = j + 1;
        }
        k = k + 1;
    }

    while (i <= m) {
        a[k] = buffer[i];
        i = i + 1;
        k = k + 1;
    }

    while (j <= e) {
        a[k] = buffer[j];
        j = j + 1;
        k = k + 1;
    }

    delete[] buffer;
}

void mergeSort(int a[], int s, int e) {
    if (s >= e) {
        return;
    }

    int m = (s + e) / 2;
    mergeSort(a, s, m);
    mergeSort(a, m + 1, e);
    combine(a, s, m, e);
}

void mergeSort(int a[], int n) {
    mergeSort(a, 0, n - 1);
}

void display(int a[], int n) {
    int i = 0;
    while (i < n) {
        cout << a[i] << " ";
        i++;
    }
    cout << endl;
}

int main() {
    int arr[] = {102, 293, 19, 38, 311, 1, 32, 11, 39};
    int size = sizeof(arr) / sizeof(int);

    display(arr, size);
    mergeSort(arr, size);
    display(arr, size);

    return 0;
}

ما الذي يجعلها أسرع؟

السبب الرئيسي هو أن تعقيدها الزمني في الغالب يساوي O(n log n)، وهو أفضل بكثير من O(n^2) عند التعامل مع كميات كبيرة من البيانات.

مقارنة بين أشهر خوارزميات الترتيب

كيف تختار خوارزمية الترتيب المناسبة؟

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

• إذا كنت تتعلم الأساسيات، ابدأ بـ Selection Sort وBubble Sort.
• إذا كانت البيانات صغيرة أو شبه مرتبة، فقد تكون Insertion Sort خياراً جيداً.
• إذا كنت تتعامل مع بيانات كثيرة وتريد أداءً أفضل، فغالباً ستكون Merge Sort أكثر ملاءمة.

أخطاء شائعة عند تعلم خوارزميات الترتيب

• التركيز على حفظ الكود دون فهم الفكرة.
• الخلط بين الفهرس index والقيمة نفسها.
• نسيان تحديث العدادات مثل i++ أو j-- مما يسبب حلقات لا نهائية.
• إهمال تحليل التعقيد الزمني وتأثيره على الأداء.

نصائح عملية لإتقان هذا الموضوع

1. طبّق كل خوارزمية يدوياً على مصفوفة صغيرة.
2. اكتب الكود بنفسك دون نسخ مباشر.
3. جرّب ترتيباً تصاعدياً ثم تنازلياً.
4. قارن بين عدد المقارنات والتبديلات في كل خوارزمية.
5. استخدم الرسوم أو الجداول لتتبّع حركة العناصر.

الخلاصة التقنية

فهم خوارزميات الترتيب ليس مجرد تمرين أكاديمي، بل هو أساس مهم لكل مطور يريد بناء برامج فعالة وتحليل الأداء بطريقة احترافية. الخوارزميات البسيطة مثل Selection Sort وBubble Sort وInsertion Sort ممتازة لفهم المنطق الداخلي للترتيب، بينما تمنحك Merge Sort تصوراً أكثر نضجاً عن تصميم الخوارزميات عالية الكفاءة. من الناحية التقنية، يمكن القول إن استيعاب الفروق بين O(n^2) وO(n log n) هو الخطوة التي تنقل المبرمج من كتابة كود يعمل فقط، إلى كتابة كود يعمل بكفاءة.