الفرز في C++: std::sort والمقارنات المخصصة والفرز المستقر

الفرز ليس سوى خوارزمية أخرى

في الصفحة السابقة رأيت أن المكتبة القياسية تأتي بخوارزميات جاهزة تعمل على أي نطاق عبر المُكرِّرات (iterators). الفرز هو ما ستلجأ إليه أكثر من غيره، وله صفحته الخاصة لأن به بعض الحواف الحادة: ترتيبات مخصصة، واستقرار، وقاعدة إن خالفتها أعطتك سلوكًا غير معرَّف بدلًا من إجابة خاطئة.

حصان العمل هنا هو std::sort من <algorithm>. تعطيه بداية النطاق ونهايته، فيعيد ترتيب العناصر في مكانها بترتيب تصاعدي:

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // تصاعدي، في المكان

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

لا تُصنع أي نسخة؛ المتجه نفسه يُعاد ترتيبه. خلف الكواليس، عادةً ما يكون std::sort خوارزمية introsort (فرز سريع يرتدّ إلى فرز الكومة)، ما يمنحك O(n log n) في المتوسط. وهذا في الغالب أسرع وأقل عرضة للأخطاء بكثير من كتابة فرز خاص بك.

ويعمل كذلك على مصفوفات C العادية؛ فأنت فقط تصف النطاق بالمؤشرات:

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

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // أو sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

ترتيب مخصص باستخدام مقارن

افتراضيًا، يرتّب std::sort العناصر باستخدام operator<. لترتيبها بشكل مختلف، مرّر وسيطًا ثالثًا: مقارنًا يأخذ عنصرين ويُعيد true إذا كان ينبغي للأول أن يأتي قبل الثاني.

تعبير lambda هو الخيار الطبيعي. الترتيب التنازلي هو ببساطة a > b:

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a قبل b" عندما يكون a أكبر -> تنازلي
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

للحالة الشائعة وهي الترتيب التنازلي البسيط على الأنواع المضمّنة، توفّر المكتبة حتى مقارنًا جاهزًا، وهو greater<T>() من <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // مثل a > b

المقارن هو أيضًا الطريقة للفرز حسب شيء غير القيمة نفسها؛ مثل فرز السلاسل حسب الطول بدلًا من الترتيب الأبجدي:

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

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // الكلمات الأقصر أولًا
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

استقبل معاملات المقارن عبر const& لأي شيء أكبر من بضعة بايتات (مثل string)؛ فنسخ كل عنصر في كل مقارنة هو هدر محض.

فرز البُنى (structs) حسب حقل

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

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

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

لاحظ أن Linus وDennis كلاهما في عمر 25. خرجا هنا بترتيبهما النسبي الأصلي، لكن std::sort لا يضمن ذلك. إذا كان الترتيب النسبي للعناصر المتساوية مهمًّا، فاستخدم std::stable_sort الذي يحافظ عليه (مقابل كلفة أداء بسيطة):

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // يبقى Linus قبل Dennis - ترتيب الإدخال محفوظ
    return 0;
}

لفض التعادل عمدًا - مثلًا الفرز حسب العمر ثم أبجديًا حسب الاسم - قارن المفتاح الثانوي فقط عندما يتساوى المفتاحان الأساسيان. ويجعل std::tie هذا أنيقًا:

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // العمر، ثم الاسم
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis وLinus بعمر 25، أبجديًا
    return 0;
}

فخ الترتيب الضعيف الصارم

هذا هو أخطر خطأ منفرد في الفرز بلغة C++، لأنه لا يعطيك إجابة خاطئة، بل يعطيك سلوكًا غير معرَّف، وهو ما يعني غالبًا انهيارًا أو قراءة خارج الحدود.

يتطلب std::sort أن يُعرّف مقارنك ترتيبًا ضعيفًا صارمًا. القاعدة العملية: يجب أن يكون comp(x, x) مساويًا لـ false لأي عنصر x. بعبارة أخرى، لا يكون أي عنصر أبدًا "قبل" نفسه. وهذا بالضبط ما يمنحك إياه < و>، وبالضبط ما يخرقه <= و>=:

// خطأ: يُعيد true عندما يكون a == b، مخالفًا الترتيب الضعيف الصارم.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // سلوك غير معرَّف - قد ينهار مع بعض المدخلات
});

مع <=، يدّعي المقارن أن 5 تأتي قبل 5 أخرى، وهو ادعاء متناقض. عندئذٍ قد يدفع std::sort مؤشرًا إلى ما بعد نهاية النطاق. تبدو المدخلات الصغيرة أحيانًا وكأنها تعمل، وهذا ما يجعل هذا العيب مرعبًا؛ فقد يجتاز اختباراتك وينهار في الإنتاج. والإصلاح هو ببساطة <:

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // صحيح: false عند التساوي
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

ومطبّ كلاسيكي ثانٍ: الفرز يُبطل صلاحية أي شيء يشير إلى داخل النطاق. فالمُكرِّرات والمؤشرات والفهارس التي حفظتها قبل الفرز لم تعد تشير إلى العنصر المنطقي نفسه بعده، لأن العناصر تحركت. أعِد اشتقاق أي موضع تحتاجه بعد الفرز، لا قبله أبدًا.

فرز جزء من نطاق

أحيانًا لا تحتاج إلى فرز كل شيء؛ تريد فقط الأوائل القليلة. فرز المتجه بأكمله لقراءة الثلاثة الأوائل هو إهدار. يرتّب std::partial_sort العناصر التي تطلبها فقط ويترك الباقي بترتيب غير محدَّد، وهو أرخص:

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // ضع الأصغر الثلاثة، بالترتيب، في المقدمة. الباقي غير محدَّد.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

وإن كنت تحتاج فقط إلى العنصر الوحيد الذي سيقع في موضع معيّن - كالوسيط (median) - فإن std::nth_element يقوم بعمل أقل: يضع العنصر الصحيح في ذلك الفهرس، مع كل ما هو أصغر قبله وكل ما هو أكبر بعده، وكل ذلك في O(n) في المتوسط.

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

الجأ إلى هذه عندما يكون "الفرز الكامل" أكثر مما تحتاجه المسألة فعلًا؛ فهي توفّر وقتًا حقيقيًا مع البيانات الكبيرة.

التالي: القوالب (Templates)

هل لاحظت أن std::sort نفسه تعامل مع int وstring وبنية Person الخاصة بك، وأن greater<int>() كان بإمكانه أن يصبح greater<string>() بالسهولة نفسها؟ هذه العمومية ليست سحرًا؛ إنها القوالب (templates)، الآلية التي تتيح لقطعة واحدة من الشيفرة أن تعمل مع أي نوع يضعه المستدعي. في الصفحة التالية سنرى كيف تكتب دوالّك وأصنافك المعتمدة على القوالب، بحيث تصبح شيفرتك مستقلة عن النوع تمامًا كالخوارزميات التي كنت تستخدمها.