Sorting C++: std::sort, comparator kustom, dan stable sort

Sorting hanyalah algoritma lain

Di halaman sebelumnya kamu sudah melihat bahwa library standar menyediakan algoritma siap pakai yang bekerja pada range apa pun lewat iterator. Sorting adalah algoritma yang paling sering kamu pakai, dan ia punya halaman sendiri karena ada beberapa bagian tajamnya: urutan kustom, stabilitas, dan satu aturan yang kalau dilanggar akan memberimu undefined behavior, bukan sekadar jawaban yang salah.

Andalan utamanya adalah std::sort dari <algorithm>. Kamu memberinya awal dan akhir sebuah range, lalu ia menyusun ulang elemen-elemennya di tempat dalam urutan naik:

#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());   // ascending, in place

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

Tidak ada salinan yang dibuat: vector itu sendiri yang disusun ulang. Di baliknya, std::sort biasanya berupa introsort (quicksort yang beralih ke heapsort bila perlu), dengan rata-rata O(n log n). Itu hampir selalu lebih cepat dan jauh lebih kecil kemungkinan salahnya daripada menulis algoritma sorting sendiri.

Ia juga bekerja pada array C biasa, kamu cukup menggambarkan range-nya dengan pointer:

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

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

    sort(arr, arr + n);               // or sort(begin(arr), end(arr));

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

Urutan kustom dengan comparator

Secara default std::sort mengurutkan elemen dengan operator<. Untuk mengurutkan dengan cara lain, kirim argumen ketiga: comparator yang menerima dua elemen dan mengembalikan true kalau elemen pertama harus berada sebelum elemen kedua.

Lambda sangat cocok untuk ini. Urutan menurun cukup ditulis 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 before b" when a is larger -> descending
    });

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

Untuk kasus umum urutan menurun pada tipe bawaan, library bahkan menyediakan comparator siap pakai, yaitu greater<T>() dari <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // same as a > b

Comparator juga merupakan cara untuk mengurutkan berdasarkan sesuatu selain nilainya sendiri, misalnya mengurutkan string berdasarkan panjangnya, bukan berdasarkan abjad:

#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();   // shorter words first
    });

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

Terima parameter comparator sebagai const& untuk apa pun yang lebih besar dari beberapa byte (seperti string). Menyalin setiap elemen di setiap perbandingan benar-benar pemborosan.

Mengurutkan struct berdasarkan field

Di program sungguhan kamu biasanya mengurutkan kumpulan struct berdasarkan salah satu field-nya. Comparator cukup mengambil field yang kamu pedulikan. Di sini kita mengurutkan orang berdasarkan umur, dari yang termuda:

#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;
}

Perhatikan bahwa Linus dan Dennis sama-sama berumur 25. Di sini mereka keluar dalam urutan relatif aslinya, tapi std::sort tidak menjamin hal itu. Kalau urutan relatif elemen yang sama itu penting, pakai std::stable_sort, yang mempertahankannya (dengan sedikit biaya performa):

#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 stays before Dennis - their input order is preserved
    return 0;
}

Untuk menentukan pemenang saat nilainya sama secara sengaja, misalnya mengurutkan berdasarkan umur lalu berdasarkan nama sesuai abjad, bandingkan key kedua hanya saat key utamanya sama. std::tie membuatnya rapi:

#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);  // age, then name
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis & Linus 25, alphabetical
    return 0;
}

Jebakan strict weak ordering

Ini kesalahan paling berbahaya dalam sorting di C++, karena hasilnya bukan jawaban yang salah, melainkan undefined behavior, yang sering berarti crash atau pembacaan di luar batas.

std::sort mengharuskan comparator-mu mendefinisikan strict weak ordering. Aturan praktisnya: comp(x, x) harus false untuk elemen x mana pun. Dengan kata lain, sebuah elemen tidak pernah berada "sebelum" dirinya sendiri. Itulah yang diberikan < dan >, dan itulah yang dilanggar <= dan >=:

// BUG: returns true when a == b, violating strict weak ordering.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // undefined behavior - may crash on some inputs
});

Dengan <=, comparator mengklaim bahwa 5 berada sebelum 5 yang lain, dan itu kontradiktif. std::sort lalu bisa menggeser pointer melewati ujung range. Input yang kecil kadang kelihatan berjalan normal, dan itulah yang membuat bug ini menakutkan: ia bisa lolos dari tes lalu crash di production. Solusinya cukup <:

#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;   // correct: false when equal
    });

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

Jebakan klasik kedua: sorting membuat tidak valid apa pun yang menunjuk ke dalam range itu. Iterator, pointer, dan indeks yang kamu simpan sebelum sorting tidak lagi merujuk ke elemen logis yang sama setelahnya, karena elemen-elemennya sudah berpindah. Tentukan ulang posisi yang kamu butuhkan setelah sorting, jangan sebelumnya.

Mengurutkan sebagian range

Kadang kamu tidak butuh semuanya terurut, kamu hanya ingin beberapa yang teratas. Mengurutkan seluruh vector hanya untuk membaca tiga elemen pertama itu boros. std::partial_sort hanya menyusun elemen yang kamu minta dan membiarkan sisanya dalam urutan yang tidak ditentukan, dan itu lebih murah:

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

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

    // Put the 3 smallest, in order, at the front. Rest is unspecified.
    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;
}

Kalau kamu hanya butuh satu elemen yang seharusnya berada di posisi tertentu, seperti median, std::nth_element bekerja lebih sedikit lagi: ia menaruh elemen yang tepat di indeks itu, dengan semua yang lebih kecil sebelumnya dan semua yang lebih besar sesudahnya, dengan rata-rata 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;
}

Pakai keduanya saat "terurut penuh" lebih dari yang sebenarnya dibutuhkan masalahmu. Keduanya menghemat waktu yang nyata pada data besar.

Berikutnya: template

Sudahkah kamu memperhatikan bahwa std::sort yang sama bisa menangani int, string, dan struct Person buatanmu sendiri, dan greater<int>() bisa saja menjadi greater<string>()? Keumuman itu bukan sihir, melainkan template, mekanisme yang membuat satu potong kode bisa bekerja untuk tipe apa pun yang dipasang pemanggilnya. Di halaman berikutnya kita akan melihat cara menulis fungsi dan class template sendiri, supaya kodemu bisa bekerja dengan tipe apa pun, sama seperti algoritma yang selama ini kamu pakai.