Binary search hanya bekerja pada data terurut, dan itu menjadikan sorting sebagai fondasi yang tidak bisa dilewati. Chapter ini membangun tiga algoritma sorting klasik secara manual: selection sort, insertion sort, dan merge sort. Ketiganya diukur dengan penghitung perbandingan dan penukaran yang sama, pada data yang sama, supaya perbedaan karakternya terlihat dalam angka — bukan sekadar teori. Setelah tiga implementasi manual, kita menutup dengan recap std::sort: algoritma yang seharusnya Anda pakai di kode nyata, beserta alasan kenapa memahami yang manual tetap penting.

Selection Sort: Pilih Terkecil, Taruh di Depan #

Selection sort membelah array menjadi dua bagian: depan yang sudah terurut, dan belakang yang belum. Setiap putaran, ia mencari elemen terkecil di bagian belakang lalu menukarnya ke posisi pertama bagian belakang — memperluas area terurut satu langkah. Jumlah penukarannya minimal (paling banyak n-1 kali), tetapi jumlah perbandingannya tetap n(n-1)/2 apa pun bentuk datanya.

Insertion Sort: Sisip ke Bagian Terurut #

Insertion sort juga memelihara area terurut di depan, tetapi mengambil satu elemen baru (kunci) dan menggeser elemen yang lebih besar satu tempat ke kanan sampai menemukan tempat yang cocok. Berbeda dari selection sort, jumlah kerjanya bergantung pada data: array yang sudah terurut hanya butuh n-1 perbandingan tanpa satu pun geseran. Inilah kenapa pada data 29, 10, 14, 37, 13, 5 di bawah insertion mengalahkan selection dalam perbandingan, meskipun keduanya sekelas pada kasus terburuk.

Merge Sort: Bagi Dua, Urutkan, Gabungkan #

Merge sort memakai strategi yang lebih cerdas: pecah array menjadi dua, urutkan masing-masing secara rekursif, lalu gabungkan dua bagian terurut dengan satu lintasan. Fungsi merge adalah jantungnya — dan inilah pengenalan pertama kita atas pola divide and conquer yang diperdalam dua chapter lagi. Perhatikan pada kode bahwa merge memakai <=, bukan <, supaya elemen yang sama tetap menjaga urutan asalnya (stable sort).

cpp 
// Tiga algoritma sorting manual dengan penghitung perbandingan/penukaran.
#include <iostream>
#include <string>
#include <utility>
#include <vector>

struct Statistik {
    long long perbandingan = 0;
    long long penukaran = 0;
};

// Selection sort: pilih terkecil dari sisa, taruh di depan.
void selectionSort(std::vector<int>& data, Statistik& stat) {
    int n = static_cast<int>(data.size());
    for (int i = 0; i < n - 1; ++i) {
        int indeksMin = i;
        for (int j = i + 1; j < n; ++j) {
            ++stat.perbandingan;
            if (data[j] < data[indeksMin]) indeksMin = j;
        }
        if (indeksMin != i) {
            std::swap(data[i], data[indeksMin]);
            ++stat.penukaran;
        }
    }
}

// Insertion sort: sisipkan elemen ke posisi yang tepat di bagian terurut.
void insertionSort(std::vector<int>& data, Statistik& stat) {
    for (int i = 1; i < static_cast<int>(data.size()); ++i) {
        int kunci = data[i];
        int j = i - 1;
        while (j >= 0) {
            ++stat.perbandingan;
            if (data[j] > kunci) {
                data[j + 1] = data[j];  // geser ke kanan
                ++stat.penukaran;
                --j;
            } else {
                break;
            }
        }
        data[j + 1] = kunci;
    }
}

// Merge sort: bagi dua, urutkan masing-masing, lalu gabungkan.
void merge(std::vector<int>& data, int kiri, int tengah, int kanan,
           std::vector<int>& bantu, Statistik& stat) {
    int i = kiri;
    int j = tengah + 1;
    int k = kiri;
    while (i <= tengah && j <= kanan) {
        ++stat.perbandingan;
        if (data[i] <= data[j]) bantu[k++] = data[i++];
        else bantu[k++] = data[j++];
    }
    while (i <= tengah) bantu[k++] = data[i++];
    while (j <= kanan) bantu[k++] = data[j++];
    for (int t = kiri; t <= kanan; ++t) data[t] = bantu[t];
}

void mergeSort(std::vector<int>& data, int kiri, int kanan,
               std::vector<int>& bantu, Statistik& stat) {
    if (kiri >= kanan) return;  // satu elemen: sudah terurut
    int tengah = kiri + (kanan - kiri) / 2;
    mergeSort(data, kiri, tengah, bantu, stat);
    mergeSort(data, tengah + 1, kanan, bantu, stat);
    merge(data, kiri, tengah, kanan, bantu, stat);
}

void cetak(const std::string& label, const std::vector<int>& data,
           const Statistik& stat) {
    std::cout << label << ": ";
    for (std::size_t i = 0; i < data.size(); ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << data[i];
    }
    std::cout << " | perbandingan=" << stat.perbandingan
              << ", penukaran=" << stat.penukaran << '\n';
}

int main() {
    std::vector<int> asal = {29, 10, 14, 37, 13, 5};

    std::vector<int> a = asal;
    Statistik sa;
    selectionSort(a, sa);
    cetak("selection", a, sa);

    std::vector<int> b = asal;
    Statistik sb;
    insertionSort(b, sb);
    cetak("insertion", b, sb);

    std::vector<int> c = asal;
    Statistik sc;
    std::vector<int> bantu(c.size());
    mergeSort(c, 0, static_cast<int>(c.size()) - 1, bantu, sc);
    cetak("merge    ", c, sc);
    return 0;
}

Output yang Dihasilkan:

text 
selection: 5 10 13 14 29 37 | perbandingan=15, penukaran=4
insertion: 5 10 13 14 29 37 | perbandingan=13, penukaran=10
merge    : 5 10 13 14 29 37 | perbandingan=10, penukaran=0

Bedah baris penting:

  1. Baris 7-10 (Statistik): struct kecil pembawa dua penghitung; satu objek per algoritma, tanpa variabel global.
  2. Baris 13-26 (selectionSort): loop dalam mencari indeksMin (perbandingan dihitung di baris 18); penukaran hanya dilakukan bila posisi minimum benar-benar berubah.
  3. Baris 29-45 (insertionSort): kunci disimpan sementara; while di baris 33 menggeser elemen yang lebih besar dan berhenti di tempat yang cocok; data[j + 1] = kunci menempatkan kunci.
  4. Baris 48-61 (merge): dua penunjuk i dan j menyapu dua bagian terurut; sisa elemen ditampung, lalu seluruh rentang disalin kembali.
  5. Baris 63-70 (mergeSort): basis rekursi kiri >= kanan (satu elemen sudah pasti terurut), lalu bagi, urutkan dua bagian, gabung.
  6. Baris 84-99: data yang sama {29, 10, 14, 37, 13, 5} disalin ke tiga vector terpisah supaya setiap algoritma bekerja pada kondisi awal yang identik.

Angka pada output merangkum tiga karakter: selection selalu 15 perbandingan (n=6 → 15 pasangan), insertion hemat dua perbandingan karena data kebetulan ramah, dan merge menang telak dengan 10 perbandingan berkat strategi membagi.

Tabel Kompleksitas dan Recap std::sort #

AlgoritmaTerbaikRata-rataTerburukMemori ekstraStabil
Selection sortO(n²)O(n²)O(n²)O(1)tidak
Insertion sortO(n)O(n²)O(n²)O(1)ya
Merge sortO(n log n)O(n log n)O(n log n)O(n)ya

Dari tabel muncul dua saran praktis. Pertama, insertion sort tetap berguna untuk data yang hampir terurut atau array kecil — banyak library sorting menyisipkannya sebagai langkah akhir. Kedua, merge sort adalah pilihan ketika jaminan kasus terburuk dan kestabilan diperlukan, dengan konsekuensi memori tambahan O(n).

Dalam kode produksi, gunakan std::sort. Algoritma di baliknya (introsort) memadukan quicksort, heapsort, dan insertion sort, memberi O(n log n) rata-rata sekaligus mencegah kasus terburuk kuadratik; bila kestabilan dibutuhkan, std::stable_sort adalah padanannya. Memahami ketiga algoritma manual di atas membuat Anda tahu persis apa yang dibeli dan apa yang dikorbankan oleh library itu.

Mengurutkan data adalah pertanyaan yang dijawab dengan mengulang pola kecil berulang-ulang — dan pola itu, rekursi, layak kita kuasai secara sadar. Chapter berikutnya membawa rekursi ke tingkat berikutnya: bukan sekadar menghitung, melainkan menjelajahi semua kemungkinan dengan backtracking.

Rujukan resmi: std::sort , std::stable_sort , dan std::is_sorted .