מיון ב-C++: std::sort, פונקציות השוואה ומיון יציב

מיון הוא עוד אלגוריתם

בעמוד הקודם ראיתם שהספרייה הסטנדרטית מגיעה עם אלגוריתמים מוכנים שעובדים על כל טווח דרך איטרטורים. מיון הוא זה שתשתמשו בו הכי הרבה, והוא מקבל עמוד משלו כי יש לו כמה קצוות חדים: סדרים מותאמים, יציבות, וכלל שאם שוברים אותו מקבלים התנהגות לא מוגדרת במקום תשובה שגויה.

סוס העבודה הוא 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;
}

לא נוצר עותק: ה-vector עצמו מסודר מחדש. מאחורי הקלעים 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<. כדי למיין אחרת, מעבירים ארגומנט שלישי: פונקציית השוואה (comparator) שמקבלת שני איברים ומחזירה 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 לפי שדה

בתוכניות אמיתיות בדרך כלל ממיינים אוספים של 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;
}

מלכודת ה-strict weak ordering

זו הטעות המסוכנת ביותר במיון ב-C++, כי היא לא נותנת תשובה שגויה: היא נותנת התנהגות לא מוגדרת, שלעיתים קרובות פירושה קריסה או קריאה מחוץ לגבולות.

std::sort דורש שפונקציית ההשוואה תגדיר strict weak ordering. הכלל המעשי: comp(x, x) חייב להיות false לכל איבר x. במילים אחרות, איבר אף פעם לא בא "לפני" עצמו. זה בדיוק מה ש-< ו-> נותנים, ובדיוק מה ש-<= ו->= שוברים:

// באג: מחזיר true כש-a == b, ומפר את ה-strict weak ordering.
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;
}

מלכודת קלאסית שנייה: מיון מבטל כל דבר שמצביע לתוך הטווח. איטרטורים, מצביעים ואינדקסים ששמרתם לפני המיון כבר לא מתייחסים לאותו איבר לוגי אחריו, כי האיברים זזו. חשבו מחדש כל מיקום שאתם צריכים אחרי המיון, אף פעם לא לפניו.

מיון של חלק מטווח

לפעמים לא צריך שהכול יהיה ממוין: רוצים רק את הכמה הראשונים. מיון של כל ה-vector כדי לקרוא את שלושת הראשונים הוא בזבוז. std::partial_sort מסדר רק את האיברים שביקשתם ומשאיר את השאר בסדר לא מוגדר, וזה זול יותר:

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

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

    // שמים את 3 הקטנים ביותר, לפי הסדר, בהתחלה. השאר לא מוגדר.
    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;
}

ואם צריך רק את האיבר היחיד שהיה יושב במיקום מסוים, כמו החציון, 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;
}

השתמשו בהם כש"ממוין לגמרי" זה יותר ממה שהבעיה באמת צריכה: הם חוסכים זמן של ממש על נתונים גדולים.

הבא בתור: תבניות

שמתם לב שאותו std::sort טיפל ב-int, ב-string וב-struct Person שלכם, ושאת greater<int>() אפשר היה באותה קלות להחליף ב-greater<string>()? הכלליות הזו היא לא קסם: אלה תבניות (templates), המנגנון שמאפשר לפיסת קוד אחת לעבוד עם כל טיפוס שהקורא מכניס. בעמוד הבא נראה איך לכתוב פונקציות ומחלקות תבנית משלכם, כדי שהקוד שלכם יהיה בלתי תלוי בטיפוס בדיוק כמו האלגוריתמים שהשתמשתם בהם.