Quicksort ialah sejenis pengisihan bahagi-dan-takluk yang memilih pivot, membahagi elemen kepada yang lebih kecil dan lebih besar daripadanya, kemudian mengisih setiap sisi secara rekursif. Purata O(n log n), kes terburuk O(n²).
Pembahagian meletakkan pivot pada kedudukan akhir tertib; semua di sebelah kiri lebih kecil, semua di sebelah kanan lebih besar. Rekursi pada kedua-dua belah pihak.
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]
(Pembahagian in-place digunakan dalam praktik untuk menjimatkan memori.)
| Kes | Masa | Punca |
|---|---|---|
| Terbaik/Purata | O(n log n) | pembahagian seimbang |
| Terburuk | O(n²) | sudah diisih dengan pivot yang buruk |
Quicksort in-place menggunakan O(log n) ruang timbunan.
Biasanya paling cepat dalam praktik disebabkan kecenderungan cache dan overhed rendah, dan ia in-place. Kes terburuk O(n²) dielakkan dengan pivot rawak atau median-tiga. Ia tidak stabil.
Quicksort ialah default dalam banyak perpustakaan standard kerana kecepatan kes purata yang luar biasa dan penggunaan memori yang rendah.
Memahami mengapa pemilihan pivot menyebabkan kes terburuk O(n²) mengajar pelajaran penting: kes purata dan kes terburuk boleh menyimpang dengan tajam.
Ia adalah topik temuduga kegemaran tepat kerana kehalusan itu.