Quicksort adalah algoritma sort divide-and-conquer yang memilih sebuah pivot, mempartisi elemen-elemen menjadi yang lebih kecil dan lebih besar darinya, kemudian secara rekursif mengurutkan setiap sisi. Rata-rata O(n log n), kasus terburuk O(n²).
Partisi menempatkan pivot pada posisi akhir yang sudah tersortir; semua yang di kiri lebih kecil, semua yang di kanan lebih besar. Recurse pada kedua sisi.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(Partisi in-place digunakan dalam praktik untuk menghemat memori.)
| Kasus | Waktu | Penyebab |
|---|---|---|
| Terbaik/Rata-rata | O(n log n) | partisi seimbang |
| Terburuk | O(n²) | sudah tersortir dengan pivot buruk |
Quicksort in-place menggunakan ruang stack O(log n).
Biasanya tercepat dalam praktik karena cache-friendly dan overhead rendah, dan bersifat in-place. Kasus terburuk O(n²) dihindari dengan pivot randomized atau median-of-three. Bukan stable.
Quicksort adalah default di banyak standard library karena kecepatan average-case yang sangat baik dan penggunaan memori yang rendah.
Memahami mengapa pilihan pivot menyebabkan kasus terburuk O(n²) mengajarkan pelajaran kunci: kasus rata-rata dan terburuk dapat berbeda secara tajam.
Ini adalah topik wawancara favorit justru karena nuansa tersebut.