Sorting Stabil

Stabilitas adalah properti algoritma sorting yang menentukan apakah urutan relatif elemen dengan key yang sama tetap terjaga setelah sorting. Properti ini bukan sekadar detail teknis — pada banyak skenario praktis seperti multi-key sorting dan sorting berurutan, stabilitas menentukan apakah hasil akhir benar atau salah. Beberapa algoritma (merge sort, insertion sort) stabil secara natural, sementara yang lain (selection sort, quick sort, heap sort) tidak stabil karena pertukaran jarak jauh. Pada Chapter ini kita akan membedah definisi stabilitas, mengidentifikasi algoritma mana yang stabil, dan mendemonstrasikan mengapa stabilitas krusial untuk multi-key sorting. Pada akhir chapter kita akan paham kapan harus menggunakan std::stable_sort alih-alih std::sort.

Definisi Stabilitas #

Suatu algoritma sorting disebut stabil bila untuk setiap pasangan elemen a dan b dengan key(a) == key(b) dan a muncul sebelum b pada input, maka a juga muncul sebelum b pada output.

Secara formal: bila input[i].key == input[j].key dan i < j, maka pada output juga berlaku pos(a) < pos(b).

Contoh Sederhana #

Input: {(Budi,5), (Andi,3), (Citra,5)} (sort by key ascending)

• Stabil: {(Andi,3), (Budi,5), (Citra,5)} — Budi tetap sebelum Citra.
• Tidak stabil: {(Andi,3), (Citra,5), (Budi,5)} — Citra muncul sebelum Budi.

Algoritma Mana yang Stabil #

Aturan Praktis #

• Stabil: algoritma yang membandingkan/menukar elemen bertetangga, atau menggunakan buffer output.
• Tidak stabil: algoritma yang melakukan pertukaran jarak jauh (selection sort, quick sort, heap sort).

Demonstrasi: Selection Sort Tidak Stabil #

Mari kita lihat konkret mengapa selection sort tidak stabil. Pada input dengan banyak elemen equal, pertukaran jarak jauh dapat merusak urutan relatif.

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

struct Item { int key; std::string tag; };

void selection_sort_unstable(std::vector<Item>& v) {
    int n = static_cast<int>(v.size());
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (v[j].key < v[min_idx].key) min_idx = j;
        }
        if (min_idx != i) std::swap(v[i], v[min_idx]);
    }
}

void print(const std::vector<Item>& v) {
    for (const auto& it : v) std::cout << "  key=" << it.key << " tag=" << it.tag << '\n';
}

int main() {
    std::vector<Item> a = {
        {5, "Budi"}, {3, "Andi"}, {5, "Citra"}, {3, "Dewi"},
        {1, "Eka"}, {5, "Fani"}, {3, "Gita"}, {1, "Hadi"}
    };
    std::cout << "Data awal:\n"; print(a);

    auto b = a;
    selection_sort_unstable(b);
    std::cout << "\nSelection sort (tidak stabil):\n"; print(b);

    auto c = a;
    std::stable_sort(c.begin(), c.end(),
        [](const Item& x, const Item& y){ return x.key < y.key; });
    std::cout << "\nstd::stable_sort (stabil):\n"; print(c);

    return 0;
}

Output yang Dihasilkan:

Data awal:
  key=5 tag=Budi
  key=3 tag=Andi
  key=5 tag=Citra
  key=3 tag=Dewi
  key=1 tag=Eka
  key=5 tag=Fani
  key=3 tag=Gita
  key=1 tag=Hadi

Selection sort (tidak stabil):
  key=1 tag=Eka
  key=1 tag=Hadi
  key=3 tag=Dewi
  key=3 tag=Gita
  key=3 tag=Andi
  key=5 tag=Fani
  key=5 tag=Citra
  key=5 tag=Budi

std::stable_sort (stabil):
  key=1 tag=Eka
  key=1 tag=Hadi
  key=3 tag=Andi
  key=3 tag=Dewi
  key=3 tag=Gita
  key=5 tag=Budi
  key=5 tag=Citra
  key=5 tag=Fani

Bedah Hasil #

1. Data awal: urutan tag untuk key=3 adalah Andi, Dewi, Gita; untuk key=5 adalah Budi, Citra, Fani.
2. Selection sort output:
   • key=3 urutan tag: Dewi, Gita, Andi — urutan relatif rusak.
   • key=5 urutan tag: Fani, Citra, Budi — urutan relatif rusak (terbalik dari input).
3. std::stable_sort output:
   • key=3 urutan tag: Andi, Dewi, Gita — sesuai input.
   • key=5 urutan tag: Budi, Citra, Fani — sesuai input.
4. Penyebab: selection sort memilih elemen minimum lalu menukar jarak jauh dengan v[i]. Pertukaran ini memindahkan elemen lain ke posisi yang bukan miliknya, merusak urutan relatif elemen equal.

Mengapa Stabilitas Penting #

Multi-Key Sorting #

Seringkali kita ingin mengurutkan data berdasarkan beberapa key. Contoh: daftar pesanan harus diurutkan berdasarkan pelanggan ascending, lalu untuk pelanggan yang sama berdasarkan tanggal descending.

Strategi klasik: sort paling signifikan terakhir, asalkan sort stabil.

Kode: Multi-Key Sorting #

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

struct Pesanan {
    std::string pelanggan;
    std::string tanggal;
    int total;
};

void print(const std::vector<Pesanan>& v) {
    for (const auto& p : v) {
        std::cout << "  " << p.tanggal << " | " << p.pelanggan
                  << " | Rp " << p.total << '\n';
    }
}

int main() {
    std::vector<Pesanan> pesanan = {
        {"Andi", "2024-01-15", 150000},
        {"Budi", "2024-01-10", 200000},
        {"Andi", "2024-01-20", 75000},
        {"Citra", "2024-01-15", 300000},
        {"Budi", "2024-01-05", 100000},
        {"Andi", "2024-01-15", 50000},
    };

    std::cout << "Data awal:\n"; print(pesanan);

    // Tahap 1: sort by tanggal (descending) — paling signifikan terakhir
    std::stable_sort(pesanan.begin(), pesanan.end(),
        [](const Pesanan& a, const Pesanan& b){ return a.tanggal > b.tanggal; });
    std::cout << "\nTahap 1 - sort by tanggal desc:\n"; print(pesanan);

    // Tahap 2: sort by pelanggan (ascending) — stabilitas menjaga urutan tanggal
    std::stable_sort(pesanan.begin(), pesanan.end(),
        [](const Pesanan& a, const Pesanan& b){ return a.pelanggan < b.pelanggan; });
    std::cout << "\nTahap 2 - sort by pelanggan asc (stabil):\n"; print(pesanan);

    return 0;
}

Output yang Dihasilkan:

Data awal:
  2024-01-15 | Andi | Rp 150000
  2024-01-10 | Budi | Rp 200000
  2024-01-20 | Andi | Rp 75000
  2024-01-15 | Citra | Rp 300000
  2024-01-05 | Budi | Rp 100000
  2024-01-15 | Andi | Rp 50000

Tahap 1 - sort by tanggal desc:
  2024-01-20 | Andi | Rp 75000
  2024-01-15 | Andi | Rp 150000
  2024-01-15 | Citra | Rp 300000
  2024-01-15 | Andi | Rp 50000
  2024-01-10 | Budi | Rp 200000
  2024-01-05 | Budi | Rp 100000

Tahap 2 - sort by pelanggan asc (stabil):
  2024-01-20 | Andi | Rp 75000
  2024-01-15 | Andi | Rp 150000
  2024-01-15 | Andi | Rp 50000
  2024-01-10 | Budi | Rp 200000
  2024-01-05 | Budi | Rp 100000
  2024-01-15 | Citra | Rp 300000

Bedah Kode Baris-per-Baris #

1. Tahap 1 — sort by tanggal desc: gunakan std::stable_sort dengan comparator a.tanggal > b.tanggal. Hasil: pesanan diurutkan tanggal descending.
2. Tahap 2 — sort by pelanggan asc: sort dengan comparator a.pelanggan < b.pelanggan. Krusial: sort ini harus stabil agar urutan tanggal dari tahap 1 terjaga untuk pelanggan yang sama.
3. Hasil akhir:
   • Untuk Andi: tanggal 2024-01-20, 2024-01-15, 2024-01-15 — urutan descending dari tahap 1 dipertahankan.
   • Untuk Budi: tanggal 2024-01-10, 2024-01-05 — descending.
   • Pelanggan diurutkan ascending: Andi, Budi, Citra.
4. Catatan: bila tahap 2 menggunakan std::sort (introsort, tidak stabil), urutan tanggal dalam setiap pelanggan bisa teracak — hasil multi-key sort akan salah.

Mengapa Quick Sort dan Heap Sort Tidak Stabil #

Quick Sort #

Pada partisi, pertukaran swap(v[i], v[j]) dengan i dan j berjauhan dapat memindahkan elemen equal melewati elemen equal lainnya. Misalnya, pivot dapat berakhir di antara dua elemen equal, sehingga salah satu dari elemen equal tersebut dipindahkan ke sisi berlawanan dari pivot — merusak urutan.

Heap Sort #

Operasi swap(v[0], v[end]) pada extract max memindahkan elemen terakhir ke root, lalu sift down menggeser elemen-elemen lain. Pertukaran jarak jauh ini merusak urutan relatif elemen equal.

Cara Membuat Algoritma Tidak Stabil Menjadi Stabil #

1. Tambahkan indeks asli sebagai tiebreaker — sisipkan (key, original_index) sebagai elemen, lalu sort dengan comparator if (a.key != b.key) return a.key < b.key; return a.idx < b.idx;. Trade-off: memori tambahan O(n) untuk indeks.
2. Gunakan stable selection sort — ganti swap dengan insertion shift pada selection sort.
3. Gunakan algoritma stabil secara langsung — bila stabilitas dibutuhkan, langsung pakai std::stable_sort.

std::sort vs std::stable_sort #

Aplikasi Stabilitas #

• Multi-key sorting — sort berurutan dengan beberapa key.
• User-facing sort dengan filter — pengguna memfilter lalu mengurutkan; stabilitas menjaga urutan filter.
• Stable partitioning — std::stable_partition memindahkan elemen ke depan/belakang tapi mempertahankan urutan.
• Database indexing — index sekunder tetap mengurutkan rowid untuk stabilitas.
• UI rendering — item yang tidak ter-sort tetap dalam urutan tampilan.

Ringkasan #

• Stabilitas = menjaga urutan relatif elemen dengan key equal.
• Stabil: bubble, insertion, merge, counting, radix, bucket (sort internal stabil), Tim sort.
• Tidak stabil: selection, quick, heap, shell.
• Stabilitas krusial untuk multi-key sorting — strategi “sort paling signifikan terakhir” memerlukan sort stabil pada tiap tahap.
• std::sort (introsort) tidak stabil; std::stable_sort (merge sort) stabil.
• Default ke std::sort; beralih ke std::stable_sort saat stabilitas diperlukan.

Pada chapter berikutnya kita akan membahas properti lain: in-place sorting — algoritma yang menggunakan O(1) memori tambahan.