سلسلة ++c للمحترفين الترتيب (Sorting) في Cpp

الترتيب وحاويات التسلسلات

std::sort هي خوارزمية لتَرتيب مجموعة من القي، وتوجد في ترويسة المكتبة القياسية ‎algorithm‎، وهي مُعرّفة بواسطة زوج من المُكرّرات. وتأخذ ‎std::sort‎ كائنًا داليًّا كمعامل أخير للموازنة بين قيمتين، ثم تحدد الترتيب بناءً على ذلك. لاحظ أنّ ‎std::sort‎ ليست مستقرة.

يجب أن تفرض دالّة الموازنة ترتيبًا صارمًا وضعيفًا على العناصر. وعمومًا فإن عامل الموازنة => و =< كافيان. وتُستخدم خوارزمية ‎std::sort‎ لترتيب حاوية ذات مُكرّر وصول عشوائي (random-access iterators):

الإصدار ≥ C++‎ 11

#include <vector>
#include <algorithm>

std::vector<int> MyVector = {3, 1, 2}

// < المقارنة الافتراضية لــ
std::sort(MyVector.begin(), MyVector.end());

تتطلّب std::sort أن تكون المكرِّرات عشوائية الوصول، ولا توفّر الحاويَتان std::list و std::forward_list (منذ C++‎ 11) مُكرِّرات وصول عشوائي، لذا لا يمكن استخدامهما مع std::sort. لكن لديهما دالة ‎sort‎ التابعة، والتي تقدّم خوارزميةَ ترتيبٍ تعمل مع أنواع المكرّرات الخاصّة بها.

الإصدار ≥ C++‎ 11

#include <list>
#include <algorithm>

std::list<int> MyList = {3, 1, 2}

// < المقارنة الافتراضية لــ
// ترتيب القائمة كاملة 
MyList.sort();

ترتب الدالة ‎sort‎ القائمة بأكملها دائمًا، لذا لا يمكنها ترتيب مجموعة فرعية (sub-range) من العناصر، لكن بأي حال بما أن لكلٍّ من القوائم (‎list‎) والقوائم الأمامية ‎forward_list‎ عمليات ربط سريعة (fast splicing operations)، فتستطيع استخراج العناصر التي تريد ترتيبها من القائمة ثم ترتِّبها، ثم تعيدها حيث كانت على النحو التالي:

void sort_sublist(std::list < int > & mylist, std::list < int > ::const_iterator start,
    std::list < int > ::const_iterator end) {
    // استخراج وترتيب المجال الفرعي المحدد
    std::list < int > tmp;
    tmp.splice(tmp.begin(), list, start, end);
    tmp.sort();
    // إعادة المجال حيث كان
    list.splice(end, tmp);
}

الترتيب باستخدام std::map تصاعديًا وتنازليًا

يرتّب هذا المثال عناصر قاموس تصاعديًا بحسب المفتاح، وتستطيع استخدام أي نوع بما في ذلك الصنف بدلًا من std::string، انظر المثال التالي:

#include <iostream>
#include <utility>
#include <map>

int main() {
    std::map < double, std::string > sorted_map;
    // ترتيب أسماء الكواكب بحسب حجمها
    sorted_map.insert(std::make_pair(0.3829, "عطارد"));
    sorted_map.insert(std::make_pair(0.9499, "الزهرة"));
    sorted_map.insert(std::make_pair(1, "الأرض"));
    sorted_map.insert(std::make_pair(0.532, "المريخ"));
    sorted_map.insert(std::make_pair(10.97, "المشتري"));
    sorted_map.insert(std::make_pair(9.14, "زحل"));
    sorted_map.insert(std::make_pair(3.981, "أورانوس"));
    sorted_map.insert(std::make_pair(3.865, "نبتون"));
    for (auto
        const & entry: sorted_map) {
        std::cout << entry.second << " (" << entry.first << " من قطر الأرض)" << '\n';
    }
}

الناتج سيكون:

(عطارد (0.3829 من قطر الأرض
(المريخ (0.532 من قطر الأرض
(الزهرة (0.9499 من قطر الأرض
(الأرض (1 من قطر الأرض
(نبتون (3.865 من قطر الأرض
(أورانوس (3.981 من قطر الأرض
(زحل (9.14 من قطر الأرض
(المشتري (10.97من قطر الأرض

إذا كانت هناك مُدخلات ذات مفاتيح متساوية، فاستخدم القاموس المتعدّد ‎multimap‎ بدلًا من القاموس ‎map‎ (كما في المثال أدناه).

لترتيب العناصر تنازليا، أعلِن عن القاموس باستخدام عامل موازنة مناسب (‎std::greater<>‎):

#include <iostream>
#include <utility>
#include <map>

int main() {
    std::multimap < int, std::string, std::greater < int >> sorted_map;
    // ترتيب أسماء الحيوانات تنازليا بحسب عدد الأرجل
    sorted_map.insert(std::make_pair(6, "حشرة"));
    sorted_map.insert(std::make_pair(4, "قطة"));
    sorted_map.insert(std::make_pair(100, "الحريشية"));
    sorted_map.insert(std::make_pair(2, "دجاجة"));
    sorted_map.insert(std::make_pair(0, "سمكة"));
    sorted_map.insert(std::make_pair(4, "فرس"));
    sorted_map.insert(std::make_pair(8, "عنكبوت"));
    for (auto
        const & entry: sorted_map) {
        std::cout << entry.second << " لها " << entry.first << " أرجل" << '\n';
    }
}

الناتج سيكون:

الحريشية لها 100 أرجل
العنكبوت لها 8 أرجل
الحشرة لها 6 أرجل
القطة لها 4 أرجل
الفرس لها 4 أرجل
الدجاجة لها 2 أرجل
السمكة لها 0 أرجل

ترتيب حاويات التسلسل باستخدام عامل "أصغر من"

سيرتِّب ‎std::sort‎ العناصر، إذا لم تُمرَّر أيّ دالة ترتيب، من خلال استدعاء العامل ‎operator<‎ على أزواج من العناصر، ويجب أن تُعيد نوعًا يمكن تحويله إلى قيمة بوليانية ‎bool‎، وتحتوي الأنواع الأساسية (مثل الأعداد الصحيحة، والعشرية، والمؤشرات…) على عوامل موازنة.

نستطيع زيادة تحميل هذا العامل لجعل استدعاء ‎sort‎ الافتراضي يعمل على الأنواع المُعرّفة من قبل المستخدم. انظر:

// تضمين حاويات التسلسل
#include <vector>
#include <deque>
#include <list>

// تضمن خوارزمية الترتيب
#include <algorithm>

class Base {
    public:
        // v على القيمة variable منشئ يضبط 
        Base(int v): variable(v) {}

وهنا استخدم variable لتتيح عامل الترتيب الكامل "أصغر من" أو less، وستمثل this الجانب الأيسر من الموازنة دومًا، نتابع:

        bool operator < (const Base & b) const {
        return this -> variable < b.variable;
    }

    int variable;
};
int main() {
    std::vector < Base > vector;
    std::deque < Base > deque;
    std::list < Base > list;

أنشئ هنا عنصرين لترتيبهما:

    Base a(10);
    Base b(5);

والآن أدرجهما في نهاية الحاوية:

    vector.push_back(a);
    vector.push_back(b);

    deque.push_back(a);
    deque.push_back(b);

    list.push_back(a);
    list.push_back(b);

والآن، رتب البيانات باستخدام دالة (operator<(const Base &b:

    std::sort(vector.begin(), vector.end());
    std::sort(deque.begin(), deque.end());
    // بشكل مختلف List ينبغي ترتيب القائمة
    list.sort();
    return 0;
}

ترتيب التسلسلات باستخدام دوال الموازنة

إليك المثال التوضيحي التالي:

// تضمين التسلسلات
#include <vector>
#include <deque>
#include <list>

 // أدخل خوارزمية الترتيب
#include <algorithm>

class Base {
    public:
        // v على القيمة variable منشئ يضبط 
        Base(int v): variable(v) {}

    int variable;
};
bool compare(const Base & a,
    const Base & b) {
    return a.variable < b.variable;
}
int main() {
    std::vector < Base > vector;
    std::deque < Base > deque;
    std::list < Base > list;

أنشئ عنصرين لترتيبهما:

    Base a(10);
    Base b(5);

أدرج عنصرين في نهاية الحاوية:

    vector.push_back(a);
    vector.push_back(b);

    deque.push_back(a);
    deque.push_back(b);

    list.push_back(a);
    list.push_back(b);

رتب البيانات باستخدام دالة الموازنة:

    std::sort(vector.begin(), vector.end(), compare);
    std::sort(deque.begin(), deque.end(), compare);
    list.sort(compare);
    return 0;
}

ترتيب التسلسلات باستخدام تعابير لامدا lambda (‏‏C++‎ 11)

انظر المثال التوضيحي التالي:

الإصدار ≥ C++‎ 11

// تضمين التسلسلات
#include <vector>
#include <deque>
#include <list>
#include <array>
#include <forward_list>

 // تضمين خوارزمية الترتيب
#include <algorithm>

class Base {
    public:
        // v على القيمة variable منشئ يضبط 
        Base(int v): variable(v) {}

    int variable;
};
int main() {
    // أنشئ عنصرين لترتيبهما
    Base a(10);
    Base b(5);

    // لذا سنستخدم قائمة تهييئ لإدراج العناصر C++11  نحن نستخدم 
   std::vector <Base> vector = {a, b};
 std::deque <Base> deque = {a, b};
 std::list <Base> list = {a, b};
 std::array <Base, 2> array = {a, b};
 std::forward_list<Base> flist = {a, b};

نستطيع ترتيب البيانات باستخدام تعبير لامدا ضمني (inline).

    std::sort(std::begin(vector), std::end(vector),
        [](const Base & a,
            const Base & b) {
            return a.variable < b.variable;
        });

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

    auto compare = [](const Base & a,
        const Base & b) {
        return a.variable < b.variable;
    };
    std::sort(std::begin(deque), std::end(deque), compare);
    std::sort(std::begin(array), std::end(array), compare);
    list.sort(compare);
    flist.sort(compare);
    return 0;
}

ترتيب المصفوفات المبنية مسبقًا

ترتّب خوارزمية ‎sort‎ التسلسلات المُعرّفة بواسطة المُكرِّرات، وهذا كاف لترتيب مصفوفة ما مبنية مسبًا (تُعرَف أيضًا باسم مصفوفات من نمط C).

الإصدار ≥ C++‎ 11

int arr1[] = {36, 24, 42, 60, 59}; 

// ترتيب الأعداد تصاعديا
sort(std::begin(arr1), std::end(arr1));

// ترتيب الأعداد تنازليا
sort(std::begin(arr1), std::end(arr1), std::greater < int > ());

قبل الإصدار C++‎ 11، كان من اللازم حساب نهاية المصفوفة باستخدام حجمها:

الإصدار < C++‎ 11

// استخدام قيمة مباشرة
sort(arr1, arr1 + 5);

// استخدام تعبير كحل بديل
const size_t arr1_size = sizeof(arr1) / sizeof( * arr1);
sort(arr1, arr1 + arr1_size);

ترتيب تسلسل باستخدام ترتيب مخصّص

إن كانت للقيم الموجودة في الحاوية عوامل مُحمّلة تحميلًا زائدًا، فنستخدم ‎std::sort‎ مع كائن دالّي مُخصّص لترتيب عناصر الحاوية تصاعديًا أو تنازليًا:

الإصدار ≥ C++‎ 11

#include <vector>
#include <algorithm>
#include <functional>

std::vector v = {5,1,2,4,3}; 

// (1,2,3,4,5) الترتيب التصاعدي
std::sort(v.begin(), v.end(), std::less < int > ());

// أو
std::sort(v.begin(), v.end());

// (5,4,3,2,1) الترتيب التنازلي
std::sort(v.begin(), v.end(), std::greater < int > ());

// أو
std::sort(v.rbegin(), v.rend());

الإصدار ≥ C++‎ 14

في الإصدار C++‎ 14، ليس علينا تمرير وسيط القالب لدوالّ الموازنة، إذ يمكن استنتاج ذلك استنادًا إلى ما تم تمريره:

std::sort(v.begin(), v.end(), std::less<>()); // ترتيب تصاعدي
std::sort(v.begin(), v.end(), std::greater<>()); // ترتيب تنازلي

هذا الدرس جزء من سلسلة دروس عن C++‎.

ترجمة -بتصرّف- للفصل Chapter 67: Sorting من كتاب C++ Notes for Professionals