الترتيب (Sorting)

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

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

ترتيب الاختيار (Selection sort)

الفكرة

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

خطوة بخطوة:

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

مثال

لنفترض أن لدينا:

[5, 8, 3, 4, 2]

نجد أصغر عنصر وهو \(2\). ثم نقوم بتبديله مع أول عنصر في المصفوفة، وهو \(5\). تصبح المصفوفة:

[2, 8, 3, 4, 5]

الآن نريد وضع ثاني أصغر عنصر في الموقع الثاني. نجد الأصغر بين \([8,3,4,5]\)، وهو \(3\)، ونتبادله مع العنصر الثاني \(8\). تصبح المصفوفة:

[2, 3, 8, 4, 5]

التالي، نجد ثالث أصغر عنصر بين \([8,4,5]\)، وهو \(4\). نبدله مع العنصر الثالث \(8\):

[2, 3, 4, 8, 5]

في الخطوة الأخيرة، نريد رابع أصغر عنصر بين \([5,8]\)، وهو \(5\). نبدله مع العنصر الرابع \(8\):

[2, 3, 4, 5, 8]

المصفوفة أصبحت مرتبة.

كود

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

int main() {
    vector<int> arr = {5, 8, 3, 4, 2};
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }

    for (int x : arr) 
        cout << x << ' ';
    cout << '\n';
}

المخرجات:

2 3 4 5 8

ترتيب الاختيار سهل الفهم، لكنه غير فعال جدًا.

التعقيد الزمني

• هناك حلقتان متداخلتان.
• لذا يستغرق تقريبًا \(n \cdot n\) خطوة → زمن \(O(n^2)\).

استخدام الدالة المدمجة sort

في البرامج الحقيقية وبرمجة المسابقات، نادرًا ما نكتب الترتيب يدويًا. C++ توفر دالة ترتيب سريعة جدًا في المكتبة القياسية.

ترتيب vector

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = {5, 8, 3, 4, 2};
    sort(arr.begin(), arr.end());

    for (int x : arr) 
        cout << x << ' ';
    cout << '\n';
}

المخرجات:

2 3 4 5 8

السطر sort(arr.begin(), arr.end()); يرتب الـ vector بأكمله تصاعديًا.

ترتيب array عادي

يمكنك أيضًا استخدام نفس sort مع المصفوفات العادية:

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

int main() {
    int n = 5;

    int arr[] = {5, 8, 3, 4, 2}; 

    sort(arr, arr + n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << ' ';
    cout << '\n';
}

المخرجات:

2 3 4 5 8

sort(arr, arr + n); يعني: رتب المصفوفة ابتداءً من arr وحتى arr + n (بعد آخر عنصر).

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

إذا أردت الترتيب من الأكبر إلى الأصغر، استخدم مقارنة مخصصة:

لـ vector:

sort(arr.begin(), arr.end(), greater<int>());

أو باستخدام iterators مع العكس:

sort(arr.rbegin(), arr.rend());

للمصفوفة العادية:

sort(arr, arr + n, greater<int>());

المخرجات:

8 5 4 3 2

ترتيب أنواع أخرى

الدالة نفسها تعمل مع strings أو doubles أو أي نوع قابل للمقارنة:

vector<string> names = {"Bob", "Alice", "Charlie"};
sort(names.begin(), names.end());

المخرجات:

Alice Bob Charlie

ترتيب بمقارنة مخصصة

يمكنك ترتيب مصفوفة حسب شروط خاصة بكتابة دالة comparator تأخذ عنصرين a و b وتعيد true إذا كان a يجب أن يأتي قبل b.

مثال: ترتيب النصوص حسب طولها:

bool comparator_by_length(string a, string b){
    int len_a = a.length();
    int len_b = b.length();

    if (len_a < len_b)
        return 1;
    else
        return 0;
}

ثم نستخدمها مع sort:

vector<string> names = {"Bob", "Alice", "Charlie"};
sort(names.begin(), names.end(), comparator_by_length);

المخرجات:

Bob Alice Charlie

ملاحظة مهمة: يجب أن تتصرف المقارنة مثل “less than” حقيقي:

• لا تتناقض
• لا تحتوي على دورات مثل a < b, b < c, و c < a

إذا كانت المقارنة غير متسقة، فإن sort سيكون سلوكه غير متوقع.

التعقيد

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

مثال:

• إذا \(n = 1,000\)، ترتيب الاختيار يقوم بحوالي \(1,000,000\) عملية.
• إذا \(n = 1,000\)، دالة sort تقوم حوالي \(10,000\) عملية — أسرع حوالي 100 مرة.