Menu
CoddyTech
START LEARNING

Quick Sort

Terakhir diperbarui

Quicksort adalah algoritma divide and conquer yang mengurutkan di sekitar sebuah "pivot". Algoritma ini memilih satu elemen pivot, lalu mempartisi array sehingga semua yang lebih kecil berada sebelum pivot dan semua yang lebih besar berada setelahnya, dan langkah ini mengunci pivot di posisi akhirnya yang terurut. Setelah itu, algoritma ini berjalan secara rekursif pada partisi kiri dan kanan. Visualisasi ini memakai skema Lomuto dengan elemen terakhir sebagai pivot. Tekan Putar untuk melihat proses partisi dan penempatan pivot.

Dalam praktik, quicksort biasanya menjadi algoritma pengurutan umum tercepat berkat perilaku cache yang baik dan partisi in-place, dengan rata-rata O(n log n). Kasus terburuknya O(n²) (misalnya array yang sudah terurut dengan pilihan pivot yang buruk), yang bisa dihindari dengan strategi pivot yang baik seperti median-of-three atau pengacakan.

Kompleksitas waktu dan ruang

KasusKompleksitasCatatan
Kasus terbaikO(n log n)Partisi seimbang
Kasus rata-rataO(n log n)Urutan acak
Kasus terburukO(n²)Pivot yang terus-menerus tidak seimbang
RuangO(log n)Stack rekursi (partisi in-place)
StabilTidakPenukaran saat partisi mengubah urutan elemen yang sama

Langkah demi langkah

LangkahApa yang terjadi
1Pilih pivot (di sini, elemen terakhir dari rentang).
2Partisi: pindahkan semua elemen yang lebih kecil daripada pivot ke kirinya.
3Tukar pivot ke batas partisi: pivot kini berada di posisi akhirnya.
4Jalankan quicksort secara rekursif pada partisi kiri.
5Jalankan quicksort secara rekursif pada partisi kanan.

Contoh penerapan

Mengurutkan [5, 2, 4, 1] dengan skema Lomuto (elemen terakhir sebagai pivot):

PutaranArrayAksi
Mulai[5, 2, 4, 1]Partisi seluruh rentang; pivot-nya 1 (elemen terakhir).
1[1, 2, 4, 5]Tidak ada yang lebih kecil daripada 1, jadi tukar 1 ke indeks 0; pivot 1 kini final. Lanjutkan secara rekursif ke kanan pada [2, 4, 5].
2[1, 2, 4, 5]Partisi [2, 4, 5] dengan pivot 5; 2 dan 4 sama-sama lebih kecil, jadi 5 tetap di akhir dan sudah final. Lanjutkan secara rekursif ke kiri pada [2, 4].
3[1, 2, 4, 5]Partisi [2, 4] dengan pivot 4; 2 lebih kecil, jadi 4 tetap di tempatnya dan sudah final. 2 adalah satu elemen, jadi sudah terurut.
Selesai[1, 2, 4, 5]Setiap pivot sudah terkunci di tempatnya; array sudah terurut.

Kapan memakai quicksort

Pakai saatHindari saat
Kamu butuh pengurutan umum yang cepat di memori dengan faktor konstanta kecil.Kamu butuh waktu kasus terburuk O(n log n) yang terjamin (pakai heap sort atau merge sort).
Memori terbatas: partisi dilakukan in-place dan hanya butuh ruang stack O(log n).Kamu butuh pengurutan stabil yang mempertahankan urutan key yang sama.
Datanya berurutan acak atau tidak diketahui dan kamu memakai pivot acak atau median-of-three.Inputnya sudah terurut atau hampir terurut dan pivot-nya tetap, sehingga memicu O(n²).
Lokalitas cache yang baik penting, karena quicksort mengakses memori secara berurutan.Kamu mengurutkan linked list, di mana merge sort tidak butuh akses acak yang diandalkan quicksort.

Kode Quick Sort

Implementasi Quick Sort yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C, Pseudocode. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.

Kode Quick Sort dalam Python

Python
1def quick_sort(a, low=0, high=None):2    if high is None:3        high = len(a) - 14    if low < high:5        p = partition(a, low, high)6        quick_sort(a, low, p - 1)7        quick_sort(a, p + 1, high)8    return a9
10
11def partition(a, low, high):12    # Lomuto partition: everything < pivot moves left of it13    pivot = a[high]14    i = low15    for j in range(low, high):16        if a[j] < pivot:17            a[i], a[j] = a[j], a[i]18            i += 119    a[i], a[high] = a[high], a[i]20    return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)
Jalankan kode ini di Playground Python

FAQ Quick Sort

Berapa kompleksitas waktu quicksort?
Quicksort rata-rata bernilai O(n log n) dan O(n log n) pada kasus terbaik, tetapi merosot menjadi O(n²) pada kasus terburuk saat partisinya terus-menerus tidak seimbang. Pivot acak atau median-of-three membuat kasus terburuk sangat kecil kemungkinannya.
Apakah quicksort stabil?

Tidak. Partisi in-place standar menukar elemen yang berjauhan, sehingga bisa mengubah urutan relatif key yang sama. Ada varian yang stabil, tetapi varian itu kehilangan keunggulan in-place milik quicksort.

Mengapa quicksort sering lebih cepat daripada merge sort?
Quicksort mempartisi secara in-place dengan lokalitas cache yang sangat baik dan tanpa buffer tambahan, jadi faktor konstantanya kecil. Merge sort menyamai batas O(n log n)-nya, tetapi harus membayar buffer O(n) dan perpindahan data yang lebih banyak.
Quicksort vs merge sort: mana yang sebaiknya dipakai?
Pilih quicksort untuk pengurutan array in-place yang cepat di memori, di mana konstantanya yang kecil biasanya menang. Pilih merge sort saat kamu butuh pengurutan stabil, kasus terburuk O(n log n) yang terjamin, atau saat kamu mengurutkan linked list atau data eksternal yang tidak muat di RAM.
Mengapa quicksort menjadi O(n²) pada array yang sudah terurut?
Dengan pivot tetap seperti elemen pertama atau terakhir, input yang sudah terurut membuat setiap partisi hanya memisahkan satu elemen, sehingga terjadi n level rekursi, bukan log n. Memilih pivot secara acak atau dengan median-of-three mematahkan pola ini dan mengembalikan perilaku O(n log n).
Apa perbedaan skema partisi Lomuto dan Hoare?

Skema Lomuto memakai satu indeks yang memindai dari kiri ke kanan dan lebih mudah ditulis, itulah sebabnya visualisasi ini memakainya. Skema Hoare memakai dua pointer yang bergerak ke dalam dan biasanya melakukan lebih sedikit penukaran, sehingga lebih cepat dalam praktik, tetapi tidak menempatkan pivot di posisi akhirnya selama langkah partisi.

Sumber terkait

Visualisasi lainnya

Ilustrasi bahasa pemrograman di Coddy

Kuasai algoritma bersama Coddy

Mulai