Quicksort

Quicksort adalah algoritma sorting paling populer di praktik karena kinerja rata-rata O(n log n) dengan konstanta kecil dan in-place (tidak butuh memori tambahan). Standard library C sendiri menyediakan qsort() yang biasanya mengimplementasikan quicksort atau variasinya. Namun, quicksort punya worst case O(n^2) yang harus diwaspadai—bila pivot selalu elemen terkecil atau terbesar, algoritma degenerasi menjadi seperti insertion sort tanpa optimisasi. Pada chapter ini kita akan mengimplementasikan quicksort dengan skema partisi Lomuto, lalu variasi dengan median-of-three pivot selection untuk menghindari worst case.

Strategi Quicksort #

Quicksort juga divide-and-conquer, tetapi strateginya berbeda dari merge sort:

1. Partition: pilih satu elemen sebagai pivot, atur ulang array sehingga elemen lebih kecil dari pivot di kiri, yang lebih besar di kanan, dan pivot di tengah.
2. Recurse: sort bagian kiri dan kanan secara rekursif.

Tidak ada langkah combine eksplisit karena partisi sudah menempatkan pivot di posisi finalnya. Inilah alasan quicksort in-place. Kompleksitas average case O(n log n) muncul bila pivot membagi array menjadi dua bagian yang relatif seimbang. Worst case O(n^2) terjadi bila pivot selalu elemen ekstrem—array terurut dengan pivot selalu elemen terakhir adalah contoh klasik.

Skema Partisi Lomuto #

Skema partisi Lomuto adalah implementasi paling sederhana: pilih elemen terakhir sebagai pivot, lalu iterasi dengan dua pointer. Pointer i menandai akhir bagian “lebih kecil dari pivot”, pointer j berjalan dari awal sampai sebelum pivot. Setiap kali a[j] <= pivot, swap a[i+1] dengan a[j] dan naikkan i.

#include <stdio.h>

/* Swap dua int */
static void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

/* Partisi Lomuto: pilih pivot sebagai elemen terakhir */
static int partition_lomuto(int *a, int rendah, int tinggi) {
    int pivot = a[tinggi];
    int i = rendah - 1;
    for (int j = rendah; j < tinggi; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i + 1], &a[tinggi]);
    return i + 1;
}

/* Quicksort rekursif dengan skema Lomuto */
void quicksort(int *a, int rendah, int tinggi) {
    if (rendah < tinggi) {
        int p = partition_lomuto(a, rendah, tinggi);
        quicksort(a, rendah, p - 1);
        quicksort(a, p + 1, tinggi);
    }
}

static void cetak(const int *a, int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void) {
    int a[] = {10, 7, 8, 9, 1, 5, 3, 6, 2, 4};
    int n = sizeof(a) / sizeof(a[0]);

    printf("Sebelum: ");
    cetak(a, n);

    quicksort(a, 0, n - 1);

    printf("Setelah: ");
    cetak(a, n);

    return 0;
}

Output yang Dihasilkan:

Sebelum: 10 7 8 9 1 5 3 6 2 4 
Setelah: 1 2 3 4 5 6 7 8 9 10 

Array terurut menaik. Skema Lomuto tidak stabil karena swap dapat melompati elemen. Setelah partisi, pivot berada di posisi final—tidak akan dipindahkan lagi oleh rekursi berikutnya.

Mari kita telaah baris-baris kode di atas:

1. Baris 4-6 (swap): helper menukar dua int lewat pointer. Pakai variabel sementara t untuk menyimpan nilai sementara selama pertukaran.
2. Baris 9-19 (partition_lomuto): pilih pivot sebagai elemen terakhir (a[tinggi]). Iterasi j dari rendah sampai tinggi-1. Setiap elemen a[j] <= pivot dimasukkan ke bagian “lebih kecil” dengan swap ke posisi i+1. Pada akhir loop, swap pivot ke posisi i+1 sehingga pivot berada di antara dua bagian.
3. Baris 11 (int i = rendah - 1;): inisialisasi i di luar rentang. i berarti “indeks terakhir bagian lebih kecil”. Awalnya kosong karena belum ada elemen yang dipastikan lebih kecil.
4. Baris 12-17 (for (j ...) if (a[j] <= pivot) i++; swap): loop utama partisi. Setiap kali menemukan elemen lebih kecil, perluas bagian kiri dan swap elemen baru masuk ke posisi tersebut.
5. Baris 18 (swap(&a[i + 1], &a[tinggi]);): tukar pivot dengan elemen pertama bagian “lebih besar atau sama”. Sekarang pivot di posisi yang benar.
6. Baris 19 (return i + 1;): kembalikan indeks pivot. Pemanggil rekursi akan skip indeks ini.
7. Baris 22-28 (quicksort): base case rendah >= tinggi tidak lakukan apa-apa (sub-array 0 atau 1 elemen). Case rekursif: partisi, lalu sort kiri (rendah sampai p-1) dan kanan (p+1 sampai tinggi).

Pivot Selection: Median-of-Three #

Worst case O(n^2) pada quicksort Lomuto biasanya terjadi karena pivot selalu elemen ekstrem. Pada data terurut menaik dengan pivot a[tinggi], pivot selalu elemen terbesar—setiap partisi menghasilkan sub-array kosong di kanan dan n-1 elemen di kiri. Solusinya: pilih pivot dengan strategi median-of-three—ambil median dari elemen pertama, tengah, dan terakhir.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

static int partition_median3(int *a, int rendah, int tinggi) {
    /* Pilih median dari 3 (rendah, tengah, tinggi) sebagai pivot */
    int mid = rendah + (tinggi - rendah) / 2;
    if (a[rendah] > a[mid]) swap(&a[rendah], &a[mid]);
    if (a[rendah] > a[tinggi]) swap(&a[rendah], &a[tinggi]);
    if (a[mid] > a[tinggi]) swap(&a[mid], &a[tinggi]);
    /* Pivot adalah a[mid], pindahkan ke tinggi-1 */
    swap(&a[mid], &a[tinggi - 1]);
    int pivot = a[tinggi - 1];

    int i = rendah, j = tinggi - 1;
    while (1) {
        while (a[++i] < pivot) ;
        while (a[--j] > pivot) ;
        if (i >= j) break;
        swap(&a[i], &a[j]);
    }
    swap(&a[i], &a[tinggi - 1]);
    return i;
}

void quicksort(int *a, int rendah, int tinggi) {
    if (tinggi - rendah < 2) {
        if (rendah < tinggi && a[rendah] > a[tinggi])
            swap(&a[rendah], &a[tinggi]);
        return;
    }
    int p = partition_median3(a, rendah, tinggi);
    quicksort(a, rendah, p - 1);
    quicksort(a, p + 1, tinggi);
}

int main(void) {
    int n = 20;
    int *a = malloc(sizeof(int) * (size_t)n);

    srand(42);
    for (int i = 0; i < n; i++) a[i] = rand() % 100;

    printf("Sebelum: ");
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");

    quicksort(a, 0, n - 1);

    printf("Setelah: ");
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");

    free(a);
    return 0;
}

Output yang Dihasilkan:

Sebelum: 66 40 81 41 12 58 21 40 35 43 74 43 17 4 96 62 92 48 98 59 
Setelah: 4 12 17 21 35 40 40 41 43 43 48 58 59 62 66 74 81 92 96 98 

Strategi median-of-three menjamin pivot bukan elemen ekstrem, sehingga partisi selalu menghasilkan dua sub-array yang tidak kosong. Pada sub-array dengan kurang dari 2 elemen, quicksort beralih ke insertion-sort manual sederhana—menghindari overhead rekursi untuk kasus trivial.

Kompleksitas dan Worst Case #

Tabel berikut merangkum karakteristik quicksort:

Menggunakan qsort() Standar #

C standard library menyediakan qsort() dari <stdlib.h>. Implementasinya bervariasi—biasanya quicksort dengan optimisasi tambahan (introsort, fall back ke heap sort bila rekursi terlalu dalam). Kita tidak perlu menulis sendiri quicksort bila yang kita butuhkan hanyalah sorting biasa.

#include <stdio.h>
#include <stdlib.h>

static int cmp_int(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    return (a > b) - (a < b);
}

int main(void) {
    int a[] = {10, 7, 8, 9, 1, 5, 3, 6, 2, 4};
    size_t n = sizeof(a) / sizeof(a[0]);

    qsort(a, n, sizeof(int), cmp_int);

    for (size_t i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Output yang Dihasilkan:

1 2 3 4 5 6 7 8 9 10 

Fungsi qsort() generik memakai comparator callback dengan signature int (*)(const void *, const void *). Pola comparator (a > b) - (a < b) aman dari overflow dan menghasilkan -1, 0, atau 1 sesuai konvensi qsort. Pakai qsort() untuk produksi—tulis sendiri hanya bila butuh kontrol penuh atas strategi pivot atau stabilitas.