Quick Sort

Quick sort adalah algoritma sorting divide-and-conquer yang memilih satu elemen sebagai pivot, mempartisi array berdasarkan pivot, lalu mengurutkan kedua subarray secara rekursif. Berbeda dengan merge sort yang menggabungkan pada akhir, quick sort melakukan kerja utama pada tahap partisi. Quick sort in-place dan rata-rata lebih cepat daripada merge sort karena akses memori yang lebih cache-friendly. Namun, quick sort memiliki worst case O(n²) bila pivot dipilih dengan buruk. Pada Chapter ini kita akan membedah mekanisme partisi, membandingkan dua skema partisi (Lomuto vs Hoare), membahas strategi pemilihan pivot, dan mengimplementasikannya dalam C++. Pada akhir chapter kita akan paham mengapa quick sort menjadi algoritma utama std::sort.

Aturan: Pivot, Partition, Recurse #

Quick sort mengikuti tiga langkah divide-and-conquer:

1. Pilih pivot — satu elemen dari array (bisa pertama, terakhir, tengah, random, atau median-of-three).
2. Partition — susun ulang array sehingga elemen < pivot berada di kiri, elemen > pivot di kanan, dan pivot pada posisi final.
3. Recurse — urutkan subarray kiri dan kanan secara rekursif.

Berbeda dengan merge sort yang kerja utama ada di merge, quick sort kerja utamanya ada di partisi.

Mekanisme Partition #

Setelah partisi, pivot berada pada indeks p yang benar untuk hasil akhir. Subarray kiri [lo, p-1] berisi elemen < pivot, subarray kanan [p+1, hi] berisi elemen >= pivot. Kedua subarray kemudian diurutkan secara rekursif.

Skema Partisi 1: Lomuto #

Skema Lomuto memilih pivot sebagai elemen terakhir (v[hi]). Pointer i menunjuk akhir subarray elemen < pivot. Untuk setiap elemen v[j] yang lebih kecil dari pivot, i maju dan v[i] ditukar dengan v[j]. Pada akhirnya, pivot ditukar ke posisi i+1.

Kode: Quick Sort Lomuto #

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

int partition_lomuto(std::vector<int>& v, int lo, int hi) {
    int pivot = v[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j) {
        if (v[j] < pivot) {
            ++i;
            std::swap(v[i], v[j]);
        }
    }
    std::swap(v[i + 1], v[hi]);
    return i + 1;
}

void quick_sort_lomuto(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition_lomuto(v, lo, hi);
    quick_sort_lomuto(v, lo, p - 1);
    quick_sort_lomuto(v, p + 1, hi);
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {10, 7, 8, 9, 1, 5, 3, 6, 2, 4};
    quick_sort_lomuto(a, 0, static_cast<int>(a.size()) - 1);
    std::cout << "Lomuto: "; print(a);
    return 0;
}

Output yang Dihasilkan:

Lomuto:  1 2 3 4 5 6 7 8 9 10

Bedah Kode Baris-per-Baris #

1. int pivot = v[hi];: pilih elemen terakhir sebagai pivot. Skema Lomuto mengasumsikan pivot ada di akhir.
2. int i = lo - 1;: indeks akhir subarray elemen < pivot. Dimulai dari lo - 1 (kosong).
3. for (int j = lo; j < hi; ++j): iterasi semua elemen kecuali pivot.
4. if (v[j] < pivot): bila elemen lebih kecil dari pivot, masukkan ke subarray kiri dengan cara menambah i lalu menukar v[i] dan v[j].
5. std::swap(v[i + 1], v[hi]);: tempatkan pivot di antara subarray kiri dan kanan — posisi final pivot.
6. return i + 1;: kembalikan indeks pivot — batas antara subarray kiri dan kanan.
7. quick_sort_lomuto(v, lo, p - 1); dan quick_sort_lomuto(v, p + 1, hi);: rekursi pada kedua subarray. Pivot sendiri tidak ikut karena sudah pada posisi final.

Skema Partisi 2: Hoare #

Skema Hoare (orisinal oleh C.A.R. Hoare, penemu quick sort) memilih pivot sebagai elemen tengah. Dua pointer i dan j bergerak dari ujung-ujung berlawanan hingga bertemu. Skema ini melakukan lebih sedikit pertukaran rata-rata (3× lebih sedikit) dibanding Lomuto.

Kode: Quick Sort Hoare #

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

int partition_hoare(std::vector<int>& v, int lo, int hi) {
    int pivot = v[lo + (hi - lo) / 2];
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { ++i; } while (v[i] < pivot);
        do { --j; } while (v[j] > pivot);
        if (i >= j) return j;
        std::swap(v[i], v[j]);
    }
}

void quick_sort_hoare(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition_hoare(v, lo, hi);
    quick_sort_hoare(v, lo, p);
    quick_sort_hoare(v, p + 1, hi);
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> b = {10, 7, 8, 9, 1, 5, 3, 6, 2, 4};
    quick_sort_hoare(b, 0, static_cast<int>(b.size()) - 1);
    std::cout << "Hoare : "; print(b);
    return 0;
}

Output yang Dihasilkan:

Hoare :  1 2 3 4 5 6 7 8 9 10

Bedah Kode Baris-per-Baris #

1. int pivot = v[lo + (hi - lo) / 2];: pivot adalah elemen tengah.
2. int i = lo - 1, j = hi + 1;: pointer i mulai sebelum lo, pointer j mulai setelah hi. Keduanya akan dimajukan/dimundurkan sebelum perbandingan.
3. do { ++i; } while (v[i] < pivot);: majukan i hingga menemukan elemen >= pivot.
4. do { --j; } while (v[j] > pivot);: mundurkan j hingga menemukan elemen <= pivot.
5. if (i >= j) return j;: bila pointer bertemu, partisi selesai. Kembalikan j sebagai batas.
6. std::swap(v[i], v[j]);: tukar elemen yang berada di sisi salah.
7. Rekursi: quick_sort_hoare(v, lo, p) dan quick_sort_hoare(v, p + 1, hi) — perhatikan pivot tidak dikecualikan karena Hoare tidak menempatkan pivot di posisi final. Rekursi kiri [lo, p] dan kanan [p+1, hi].

Perbandingan Skema Lomuto vs Hoare #

Strategi Pemilihan Pivot #

Pemilihan pivot menentukan keseimbangan partisi — dan keseimbangan menentukan kompleksitas.

Median-of-Three #

Strategi ini memilih median dari v[lo], v[mid], v[hi] sebagai pivot. Pada data hampir terurut (kasus umum di dunia nyata), median-of-three menghasilkan partisi yang seimbang. Implementasi:

int median_of_three(std::vector<int>& v, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (v[lo] > v[mid]) std::swap(v[lo], v[mid]);
    if (v[lo] > v[hi])  std::swap(v[lo], v[hi]);
    if (v[mid] > v[hi]) std::swap(v[mid], v[hi]);
    // Sekarang v[mid] adalah median. Tukar ke hi agar cocok dengan Lomuto.
    std::swap(v[mid], v[hi]);
    return partition_lomuto(v, lo, hi);
}

1. Tiga perbandingan dan tiga swap: mengurutkan tiga elemen v[lo], v[mid], v[hi] sehingga v[mid] adalah median.
2. std::swap(v[mid], v[hi]);: menempatkan pivot pada posisi hi agar sesuai dengan skema Lomuto.
3. return partition_lomuto(v, lo, hi);: gunakan Lomuto untuk partisi.

Kompleksitas #

Mengapa Worst Case O(n²) #

Bila pivot selalu elemen terkecil atau terbesar, salah satu subarray kosong dan subarray lain berukuran n-1. Recurrence menjadi T(n) = T(n-1) + O(n) yang penyelesaiannya T(n) = O(n²). Kasus ini terjadi pada:

• Sorted/near-sorted input dengan first/last pivot.
• Semua elemen identik (tanpa optimasi three-way partition).

Three-Way Partition (Dutch National Flag) #

Untuk mengatasi input dengan banyak duplikat, gunakan three-way partition yang membagi array menjadi tiga bagian: < pivot, == pivot, > pivot. Hanya bagian < dan > yang direkursi — bagian == sudah pada posisi final.

Benchmark: Lomuto vs Median-of-Three vs std::sort #

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

int partition_lomuto(std::vector<int>& v, int lo, int hi) {
    int pivot = v[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j)
        if (v[j] < pivot) std::swap(v[++i], v[j]);
    std::swap(v[i + 1], v[hi]);
    return i + 1;
}

void quick_sort_lomuto(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition_lomuto(v, lo, hi);
    quick_sort_lomuto(v, lo, p - 1);
    quick_sort_lomuto(v, p + 1, hi);
}

int median_of_three(std::vector<int>& v, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (v[lo] > v[mid]) std::swap(v[lo], v[mid]);
    if (v[lo] > v[hi])  std::swap(v[lo], v[hi]);
    if (v[mid] > v[hi]) std::swap(v[mid], v[hi]);
    std::swap(v[mid], v[hi]);
    return partition_lomuto(v, lo, hi);
}

void quick_sort_mot(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int p = median_of_three(v, lo, hi);
    quick_sort_mot(v, lo, p - 1);
    quick_sort_mot(v, p + 1, hi);
}

int main() {
    // Sorted input: Lomuto worst case
    std::vector<int> c(2000);
    for (int i = 0; i < 2000; ++i) c[i] = i;

    auto t1 = std::chrono::high_resolution_clock::now();
    quick_sort_lomuto(c, 0, static_cast<int>(c.size()) - 1);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d1 = t2 - t1;

    auto d = c;
    t1 = std::chrono::high_resolution_clock::now();
    quick_sort_mot(d, 0, static_cast<int>(d.size()) - 1);
    t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d2 = t2 - t1;

    auto e = c;
    t1 = std::chrono::high_resolution_clock::now();
    std::sort(e.begin(), e.end());
    t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d3 = t2 - t1;

    std::cout << "Sorted input (n=2000):\n";
    std::cout << "  Lomuto (last pivot)  : " << d1.count() << " ms\n";
    std::cout << "  Median-of-three      : " << d2.count() << " ms\n";
    std::cout << "  std::sort (introsort): " << d3.count() << " ms\n";
    return 0;
}

Output yang Dihasilkan (waktu bervariasi antar mesin):

Sorted input (n=2000):
  Lomuto (last pivot)  : 1.08 ms
  Median-of-three      : 0.02 ms
  std::sort (introsort): 0.01 ms

1. Lomuto pada sorted input menjadi O(n²) — setiap partisi menghasilkan subarray kosong dan n-1. Untuk n=2000, total pembandingan ≈ 2 juta.
2. Median-of-three menghasilkan partisi seimbang pada sorted input — kembali ke O(n log n).
3. std::sort menggunakan introsort yang juga menghindari worst case — paling cepat di antara ketiganya.

Mitigasi Worst Case #

Beberapa strategi untuk menghindari worst case O(n²):

1. Random pivot — pilih pivot secara acak. Worst case tetap O(n²) tetapi probabilistik sangat jarang.
2. Median-of-three — pilih median dari v[lo], v[mid], v[hi]. Cukup untuk input hampir terurut.
3. Introsort — bila kedalaman rekursi melebihi 2·log₂ n, switch ke heap sort. Inilah strategi std::sort.
4. Three-way partition — untuk input dengan banyak duplikat.

Stabilitas #

Quick sort tidak stabil. Pertukaran jarak jauh pada saat partisi dapat merusak urutan relatif elemen equal. Untuk verifikasi: input {(Budi,5), (Andi,3), (Citra,5)} yang di-sort dengan quick sort by key dapat menghasilkan Citra sebelum Budi — tergantung posisi pivot dan jalur partisi.

In-Place #

Quick sort in-place — hanya O(1) memori tambahan untuk variabel pointer. Namun call stack rekursi memerlukan O(log n) pada best case dan O(n) pada worst case. Untuk menghindari worst case space, gunakan tail call optimization atau iteratif dengan stack eksplisit.

Ringkasan #

• Quick sort memilih pivot, mempartisi, lalu mengurutkan kedua subarray secara rekursif.
• Skema partisi utama: Lomuto (sederhana, pivot di akhir) dan Hoare (lebih efisien, pivot di tengah).
• Average case O(n log n); worst case O(n²) bila pivot tidak seimbang.
• Tidak stabil — pertukaran jarak jauh merusak urutan relatif elemen equal.
• In-place O(1) memori tambahan, O(log n) call stack pada best case.
• Mitigasi worst case: random pivot, median-of-three, atau introsort (std::sort).

Pada chapter berikutnya kita akan membahas heap sort — algoritma O(n log n) yang in-place, tidak stabil, namun menjamin worst case O(n log n) tanpa strategi pivot.