Algorithms Library

Header <algorithm> berisi sekitar 80 algoritma generik yang bekerja pada range iterator. Alih-alih menulis loop manual untuk sort, search, atau accumulate, kita memakai algoritma yang sudah teruji dan teroptimasi — beberapa di antaranya memakai introsort dengan batas O(n log n) atau binary search dengan komparasi minimal. Pada Chapter ini kita akan membedah kategori utama: sorting, binary search, min/max, numeric accumulation, dan mutasi range. Pemilihan algoritma yang tepat sering mengubah kompleksitas solusi dari O(n²) menjadi O(n log n).

Kategori Utama <algorithm> #

Mekanisme: Sorting dan Kompleksitas #

std::sort memakai introsort — kombinasi quicksort + heapsort. Awalnya quicksort; bila kedalaman rekursi melebihi 2·log n, algoritma beralih ke heapsort untuk menjaga worst-case tetap O(n log n). Kompleksitas rata-rata dan worst-case sama-sama O(n log n).

std::stable_sort mempertahankan urutan relatif elemen yang setara — biasanya merge sort — kompleksitas O(n log n) bila memori cukup, O(n log² n) bila tidak.

std::partial_sort(b, m, e) menempatkan m - b elemen terkecil di awal range terurut; sisanya tidak terurut. Berguna untuk query top-k dalam O(n log k).

std::nth_element(b, nth, e) menempatkan elemen yang akan berada pada posisi nth bila range diurutkan; elemen kiri lebih kecil, elemen kanan lebih besar — tidak terurut. Kompleksitas rata-rata O(n).

Kode: Algoritma Umum #

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>

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

    // 1) sort, stable_sort, partial_sort, nth_element
    std::vector<int> a = v;
    std::sort(a.begin(), a.end());
    std::cout << "sort           : ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';

    // partial_sort: 3 terkecil di awal terurut
    std::vector<int> b = v;
    std::partial_sort(b.begin(), b.begin() + 3, b.end());
    std::cout << "partial_sort 3 : ";
    for (int x : b) std::cout << x << ' ';
    std::cout << '\n';

    // nth_element: elemen ke-4 (index 3) berada di posisi akhir
    std::vector<int> c = v;
    std::nth_element(c.begin(), c.begin() + 3, c.end());
    std::cout << "nth_element 3  : ";
    for (int x : c) std::cout << x << ' ';
    std::cout << "(elemen ke-4 = " << c[3] << ")\n";

    // 2) binary_search, lower_bound, upper_bound
    std::vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << std::boolalpha;
    std::cout << "binary_search(5) = " << std::binary_search(sorted.begin(), sorted.end(), 5) << '\n';
    std::cout << "binary_search(99) = " << std::binary_search(sorted.begin(), sorted.end(), 99) << '\n';
    std::cout << "lower_bound(5) idx = " << (std::lower_bound(sorted.begin(), sorted.end(), 5) - sorted.begin()) << '\n';
    std::cout << "upper_bound(5) idx = " << (std::upper_bound(sorted.begin(), sorted.end(), 5) - sorted.begin()) << '\n';

    // 3) min, max, minmax
    std::cout << "min(3, 7)      = " << std::min(3, 7) << '\n';
    std::cout << "max(3, 7)      = " << std::max(3, 7) << '\n';
    auto [mn, mx] = std::minmax({5, 2, 8, 1, 9});
    std::cout << "minmax         = " << mn << ' ' << mx << '\n';

    // 4) accumulate, partial_sum
    std::vector<int> d = {1, 2, 3, 4, 5};
    int sum = std::accumulate(d.begin(), d.end(), 0);
    int prod = std::accumulate(d.begin(), d.end(), 1, std::multiplies<int>());
    std::cout << "sum            = " << sum << '\n';
    std::cout << "prod           = " << prod << '\n';

    std::vector<int> prefix(d.size());
    std::partial_sum(d.begin(), d.end(), prefix.begin());
    std::cout << "partial_sum    : ";
    for (int x : prefix) std::cout << x << ' ';
    std::cout << '\n';

    // 5) find, count, reverse, unique
    std::vector<int> e = {1, 2, 2, 3, 3, 3, 4};
    std::cout << "count(3)       = " << std::count(e.begin(), e.end(), 3) << '\n';
    auto fit = std::find(e.begin(), e.end(), 3);
    if (fit != e.end()) std::cout << "find(3) at idx = " << (fit - e.begin()) << '\n';

    std::vector<int> f = {1, 1, 2, 2, 2, 3, 4, 4, 5};
    auto last = std::unique(f.begin(), f.end());  // kompak (harus sorted)
    f.erase(last, f.end());
    std::cout << "unique         : ";
    for (int x : f) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

sort           : 1 2 3 4 5 6 7 8 9 
partial_sort 3 : 1 2 3 8 9 5 7 4 6 
nth_element 3  : 2 1 3 4 5 6 7 9 8 (elemen ke-4 = 4)
binary_search(5) = true
binary_search(99) = false
lower_bound(5) idx = 4
upper_bound(5) idx = 5
min(3, 7)      = 3
max(3, 7)      = 7
minmax         = 1 9
sum            = 15
prod           = 120
partial_sum    : 1 3 6 10 15 
count(3)       = 3
find(3) at idx = 3
unique         : 1 2 3 4 5 

Bedah Kode Baris-per-Baris #

1. std::sort(a.begin(), a.end()): introsort, O(n log n). Default comparator std::less<T> sehingga mengurutkan ascending. Untuk descending: std::sort(a.begin(), a.end(), std::greater<int>()).
2. std::partial_sort(b.begin(), b.begin() + 3, b.end()): menempatkan tiga elemen terkecil di awal, terurut {1, 2, 3}. Sisanya {8, 9, 5, 7, 4, 6} tidak terurut — boleh urutan apa pun. Kompleksitas O(n log k) dengan k = 3.
3. std::nth_element(c.begin(), c.begin() + 3, c.end()): menempatkan elemen ke-4 (yang akan di index 3 bila sorted) pada posisi c[3] = 4. Elemen kiri {2, 1, 3} lebih kecil dari 4, elemen kanan {5, 6, 7, 9, 8} lebih besar. Kompleksitas rata-rata O(n).
4. std::binary_search(sorted.begin(), sorted.end(), 5): hanya mengembalikan bool — elemen ada atau tidak. Bila butuh posisi, pakai lower_bound. Mengasumsikan range sudah sorted.
5. std::lower_bound(...): iterator ke elemen pertama >= 5. Pada {1..9} indeks 4 (elemen 5). O(log n).
6. std::upper_bound(...): iterator ke elemen pertama > 5. Indeks 5 (elemen 6). Selisih upper_bound - lower_bound menghasilkan jumlah elemen sama dengan 5.
7. std::min(3, 7) / std::max(3, 7): bekerja untuk dua nilai. Bila butuh lebih dari dua, pakai std::min({a, b, c, d}) (initializer list).
8. std::minmax({...}): C++11, mengembalikan std::pair (min, max). Structured binding C++17 mengurai keduanya menjadi mn dan mx.
9. std::accumulate(d.begin(), d.end(), 0): penjumlahan dengan initial value 0. Awat penting: tipe accumulator mengikuti initial value. accumulate(begin, end, 0) untuk vector<long long> akan menjadi int — bisa overflow. Selalu tulis 0LL untuk data besar.
10. std::accumulate(..., 1, std::multiplies<int>()): ganti operasi jadi perkalian dengan initial 1 → hasil 1*1*2*3*4*5 = 120. Pola umum untuk reduce generik.
11. std::partial_sum(d.begin(), d.end(), prefix.begin()): prefix sum — prefix[i] = sum(d[0..i]). Output {1, 3, 6, 10, 15} untuk input {1, 2, 3, 4, 5}.
12. std::find(e.begin(), e.end(), 3): linear search O(n). Mengembalikan iterator ke elemen pertama yang sama dengan 3. Bila tidak ada, kembalikan e.end().
13. std::unique(f.begin(), f.end()): menghapus duplikat berdekatan — bukan duplikat global. Range harus sudah sorted. Mengembalikan iterator past-the-end dari range yang sudah dikompak; sisa elemen di akhir tidak terdefinisi, biasanya di-erase.

Pola Binary Search pada Jawaban #

lower_bound/upper_bound tidak hanya untuk elemen — pola yang sama bekerja untuk binary search on answer. Contoh: cari x minimum sehingga f(x) >= target, dengan f monoton naik:

int lo = 0, hi = 1e9;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (f(mid) >= target) hi = mid;
    else lo = mid + 1;
}
// lo == jawaban minimum

Pola ini identik dengan lower_bound — lower_bound pada range diskret vs. binary search pada domain kontinu.

Ringkasan #

• <algorithm> + <numeric> menyediakan ~80 algoritma generik berbasis iterator.
• Sorting: sort (O(n log n)), stable_sort, partial_sort (top-k), nth_element (k-th dalam O(n) rata-rata).
• Binary search pada sorted range: binary_search (bool), lower_bound/upper_bound (posisi).
• Numeric: accumulate (hati-hati tipe initial value), partial_sum (prefix), iota (isi 0,1,2,…).
• Mutasi: reverse, rotate, unique (harus sorted), shuffle.
• Bila menulis binary search manual, gunakan pola lo + (hi - lo) / 2 untuk menghindari overflow.