Penjelasan quicksort: cara kerja, kode, dan kompleksitas

Ide dasar dengan kata-kata sederhana

1. Pilih elemen pivot, misalnya elemen terakhir, atau elemen acak.
2. Partisi: pindahkan setiap elemen yang lebih kecil dari pivot ke kirinya dan setiap elemen yang lebih besar ke kanannya. Pivot kini berada di posisi akhirnya yang terurut.
3. Urutkan secara rekursif bagian di kiri pivot dan bagian di kanannya. Tidak ada yang perlu digabungkan sesudahnya.

Merge sort memecah dengan mudah dan menggabungkan dengan susah. Quicksort kebalikannya: partisi yang mengerjakan tugas berat, dan menyambung kedua bagian tidak butuh usaha karena keduanya sudah berada di tempat yang benar dalam array yang sama.

Contoh: satu partisi Lomuto

Partisi [10, 80, 30, 90, 40, 50, 70] dengan elemen terakhir, 70, sebagai pivot. Indeks i menandai ujung wilayah elemen yang lebih kecil dari pivot; j memindai dari kiri ke kanan.

70 kini berada di indeks 4, posisi akhirnya. Quicksort lalu mengurutkan [10, 30, 40, 50] dan [90, 80] secara terpisah.

Implementasi Python

import random

def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]       # move the pivot to the end
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo=0, hi=None):
    """Sort list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:           # recurse on the smaller side
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1
    return a

print(quicksort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]
print(quicksort([3, 3, 3, 1]))                   # [1, 3, 3, 3]

Berekursi ke sisi yang lebih kecil dan mengulang pada sisi yang lebih besar menjaga kedalaman stack tetap O(log n) bahkan pada kasus terburuk. Versi singkat yang tidak in-place populer untuk menjelaskan idenya, tetapi mengalokasikan list baru di setiap tingkat:

def quicksort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort_simple(less) + equal + quicksort_simple(greater)

print(quicksort_simple([5, 2, 9, 2, 7]))   # [2, 2, 5, 7, 9]

Kompleksitas waktu dan ruang

Kasus terburuk klasik adalah pivot tetap berupa elemen pertama atau terakhir pada input yang sudah terurut atau terurut terbalik: setiap partisi hanya menyingkirkan pivot, menghasilkan n tingkat dengan pekerjaan O(n). Pivot acak membuat hal ini sangat tidak mungkin untuk input apa pun.

Perbandingan quicksort dengan sort lain

Quicksort tidak stabil: pertukaran saat partisi bisa memindahkan elemen melewati elemen yang sama. Biasanya ia mengalahkan merge sort dan heapsort pada array di memori karena perulangan dalamnya sederhana, bekerja di tempat, dan mengakses memori secara kebanyakan berurutan. Introsort, yang dipakai banyak implementasi std::sort pustaka standar C++, memulai dengan quicksort dan beralih ke heapsort jika rekursi terlalu dalam, sehingga O(n log n) terjamin.

Pilihan pivot, varian, dan kesalahan umum

• Pilihan pivot: elemen pertama atau terakhir (sederhana, tetapi O(n²) pada input terurut), elemen acak, atau median dari tiga (pertama, tengah, terakhir).
• Partisi Hoare: dua indeks bergerak saling mendekat dan menukar pasangan yang berada di sisi yang salah. Rata-rata melakukan lebih sedikit pertukaran daripada Lomuto.
• Partisi tiga arah (Dutch national flag): membagi menjadi lebih kecil, sama, dan lebih besar. Ini membuat array dengan banyak kunci duplikat menjadi cepat; Lomuto biasa menurun menjadi O(n²) ketika semua kunci sama.
• Dual-pivot quicksort memakai dua pivot dan tiga bagian; Java memakainya untuk mengurutkan array tipe primitif.
• Quickselect memakai satu partisi dan berekursi hanya ke satu sisi untuk menemukan elemen terkecil ke-k dalam waktu rata-rata O(n).

Kapan memakai quicksort

Quicksort adalah pilihan default yang baik untuk mengurutkan array di memori ketika stabilitas tidak diperlukan. Di Python, pakai sorted() atau list.sort() saja; keduanya memakai Timsort, yang stabil dan cepat pada data yang sebagian terurut. Mengimplementasikan quicksort adalah tugas wawancara yang sangat umum, sering dilanjutkan dengan pertanyaan tentang kasus terburuk, pilihan pivot, stabilitas, atau memakai quickselect untuk mencari elemen terbesar ke-k.