Konsep Sorting

Sorting adalah proses menyusun ulang elemen-elemen suatu koleksi sehingga membentuk urutan tertentu, biasanya ascending (menaik) atau descending (menurun). Meskipun terdengar sederhana, masalah sorting menjadi salah satu topik paling kaya di DSA karena terdapat puluhan algoritma dengan karakteristik berbeda. Pemilihan algoritma yang tepat sangat memengaruhi kinerja aplikasi, mulai dari pengolahan data jutaan baris hingga antarmuka yang harus responsif. Pada Chapter ini kita akan memetakan terminologi dasar sorting: arah urutan, comparator, stabilitas, sifat in-place, serta tabel kompleksitas ringkas. Pemahaman istilah-istilah ini menjadi fondasi untuk membahas tiap algoritma sorting pada chapter-chapter berikutnya.

Arah Pengurutan: Ascending dan Descending #

Pada sorting, kita mendefinisikan relasi urutan antar elemen. Dua arah yang paling umum adalah:

Ascending — dari nilai terkecil ke nilai terbesar. Contoh: 1, 2, 3, 4, 5.
Descending — dari nilai terbesar ke nilai terkecil. Contoh: 5, 4, 3, 2, 1.

Untuk data non-numerik (misalnya string), urutan ditentukan oleh relasi yang ditetapkan, biasanya lexicographic order pada karakter. Sorting leksikografis {"banana", "apple", "cherry"} menghasilkan {"apple", "banana", "cherry"}.

Comparator: Mendefinisikan Urutan #

Comparator adalah fungsi (atau objek callable) yang menerima dua elemen dan mengembalikan true bila elemen pertama harus mendahului elemen kedua. Comparator memungkinkan kita mengubah urutan tanpa mengubah algoritma sorting itu sendiri.

Mekanisme: Strict Weak Ordering #

Comparator wajib memenuhi sifat strict weak ordering:

Irrefleksif: comp(a, a) harus false.
Asimetris: bila comp(a, b) true, maka comp(b, a) harus false.
Transitif: bila comp(a, b) dan comp(b, c) true, maka comp(a, c) harus true.
Transitifitas ekuivalensi: bila !comp(a,b) && !comp(b,a) dan !comp(b,c) && !comp(c,b), maka !comp(a,c) && !comp(c,a).

Pelanggaran sifat-sifat ini dapat menyebabkan algoritma sorting STL (seperti std::sort) menghasilkan perilaku undefined — output bisa salah, crash, atau infinite loop.

Kode: Comparator Ascending dan Descending #

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

struct Mahasiswa {
    std::string nama;
    int nilai;
};

bool asc_nilai(const Mahasiswa& a, const Mahasiswa& b) {
    return a.nilai < b.nilai;
}

bool desc_nilai(const Mahasiswa& a, const Mahasiswa& b) {
    return a.nilai > b.nilai;
}

int main() {
    std::vector<Mahasiswa> mhs = {
        {"Budi", 85}, {"Andi", 92}, {"Citra", 78}, {"Dewi", 92}
    };

    std::cout << "Data awal:\n";
    for (const auto& m : mhs) std::cout << "  " << m.nama << " = " << m.nilai << '\n';

    std::stable_sort(mhs.begin(), mhs.end(), asc_nilai);
    std::cout << "\nSetelah stable_sort ascending by nilai:\n";
    for (const auto& m : mhs) std::cout << "  " << m.nama << " = " << m.nilai << '\n';

    std::stable_sort(mhs.begin(), mhs.end(), desc_nilai);
    std::cout << "\nSetelah stable_sort descending by nilai:\n";
    for (const auto& m : mhs) std::cout << "  " << m.nama << " = " << m.nilai << '\n';

    return 0;
}

Output yang Dihasilkan:

text
Data awal:
  Budi = 85
  Andi = 92
  Citra = 78
  Dewi = 92

Setelah stable_sort ascending by nilai:
  Citra = 78
  Budi = 85
  Andi = 92
  Dewi = 92

Setelah stable_sort descending by nilai:
  Andi = 92
  Dewi = 92
  Budi = 85
  Citra = 78

Bedah Kode Baris-per-Baris #

struct Mahasiswa: tipe data gabungan yang menyimpan nama dan nilai. Inilah elemen yang akan kita sort.
bool asc_nilai(...): comparator yang mengembalikan true bila a.nilai < b.nilai. Operator < memenuhi strict weak ordering untuk int.
std::stable_sort(...): mempertahankan urutan relatif elemen yang equal — Andi dan Dewi sama-sama bernilai 92; pada ascending, Andi tetap di depan Dewi karena Andi muncul lebih awal di input.
desc_nilai: membalik relasi dengan >. Sekali lagi, std::stable_sort menjaga Andi di depan Dewi meski urutan keseluruhan descending.
Implikasi: pemilihan comparator dan pilihan std::stable_sort vs std::sort menentukan hasil akhir sorting ketika ada elemen yang equal.

Stabil vs Tidak Stabil (Preview) #

Suatu algoritma sorting disebut stabil bila algoritma tersebut mempertahankan urutan relatif elemen yang equal. Misalnya, jika Budi muncul sebelum Andi pada input dan keduanya bernilai sama, maka Budi tetap mendahului Andi pada output.

Stable	Tidak Stabil
Bubble sort, insertion sort, merge sort, counting sort, radix sort, bucket sort	Selection sort, quick sort, heap sort

Stabilitas menjadi penting saat kita melakukan sorting berbasis lebih dari satu key. Contoh: mengurutkan daftar pesanan berdasarkan tanggal descending, lalu berdasarkan pelanggan ascending — sort kedua harus stabil terhadap sort pertama agar pengelompokan per pelanggan tetap berurutan tanggal di dalamnya.

In-Place vs Tidak In-Place (Preview) #

Algoritma in-place melakukan sorting menggunakan hanya sejumlah kecil memori tambahan — biasanya O(1) selain memori untuk input itu sendiri. Sebaliknya, algoritma non in-place mengalokasikan memori tambahan yang sebanding dengan ukuran input.

In-Place	Tidak In-Place
Bubble sort, selection sort, insertion sort, quick sort, heap sort	Merge sort, counting sort, radix sort, bucket sort

In-place bukan berarti tanpa memori tambahan sama sekali. Quick sort, misalnya, menggunakan O(log n) memori untuk call stack rekursi. Heap sort dan selection sort benar-benar O(1) memori tambahan.

Tabel Kompleksitas Ringkas #

Tabel berikut memberikan ringkasan kompleksitas seluruh algoritma sorting yang akan kita pelajari pada Section ini. Kompleksitas best/average/worst dirumuskan dalam n (jumlah elemen) serta parameter tambahan (k = rentang nilai, d = banyak digit).

Algoritma	Best	Average	Worst	Space	Stable
Bubble sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Ya
Selection sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	Tidak
Insertion sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Ya
Merge sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Ya
Quick sort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	Tidak
Heap sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	Tidak
Counting sort	`O(n + k)`	`O(n + k)`	`O(n + k)`	`O(n + k)`	Ya
Radix sort	`O(d·(n + b))`	`O(d·(n + b))`	`O(d·(n + b))`	`O(n + b)`	Ya
Bucket sort	`O(n + k)`	`O(n + k)`	`O(n²)`	`O(n + k)`	Ya

Klasifikasi Berdasarkan Pendekatan #

Algoritma sorting dapat diklasifikasikan berdasarkan pendekatan utama yang dipakai:

Comparison-based — bekerja dengan membandingkan pasangan elemen. Bubble, selection, insertion, merge, quick, dan heap sort termasuk kelompok ini. Batas bawah teoritis untuk comparison-based sorting adalah Ω(n log n).
Non-comparison — tidak membandingkan elemen secara langsung. Counting sort, radix sort, dan bucket sort termasuk kelompok ini. Kompleksitas bisa O(n) pada kondisi tertentu, namun dengan batasan tipe data (harus berupa bilangan bulat atau bisa dipetakan ke indeks).
Divide and conquer — memecah masalah menjadi sub-masalah, menyelesaikan masing-masing, lalu menggabungkan. Merge sort dan quick sort adalah contoh klasik.
Distribution-based — mendistribusikan elemen ke beberapa bucket lalu mengurutkan masing-masing. Bucket sort dan radix sort termasuk kelompok ini.

Ringkasan #

Sorting menyusun elemen menjadi urutan tertentu, ascending atau descending, yang ditentukan oleh comparator.
Comparator wajib memenuhi strict weak ordering agar algoritma sorting STL bekerja dengan benar.
Stabilitas menjaga urutan relatif elemen yang equal; penting untuk multi-key sorting.
In-place menggunakan O(1) memori tambahan; non in-place mengalokasikan memori proporsional terhadap n.
Comparison-based sorting memiliki batas bawah Ω(n log n); non-comparison bisa mencapai O(n) dengan batasan tipe data.

Pada chapter-chapter berikutnya kita akan membedah setiap algoritma sorting secara mendalam, mulai dari yang paling sederhana (bubble, selection, insertion) hingga yang lebih canggih (merge, quick, heap, dan non-comparison sorts).