Quicksort iku jinis nglaras divide-and-conquer sing ndemek pivot, nggoleki unsur-unsur dadi sing luwih cilik lan luwih gedhé saka iku, banjur ngsort rekursif masing-masing sisih. Rata-rata O(n log n), kasuwan paling parah O(n²).
Partisi nglawakke pivot ing posisi akhir sing wis disort; kabeh ing kiwa luwih cilik, kabeh ing tengen luwih gedhé. Rekursi ing loro-lorone sisih.
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]
(Pemartisian in-place digunakake ing praktik kanggo nyimpen memori.)
| Kasuwan | Wektu | Sababe |
|---|---|---|
| Paling apik/Rata-rata | O(n log n) | partisi seimbang |
| Paling parah | O(n²) | wis disort karo pivot sing ala |
Quicksort in-place nggunakake O(log n) spasi stack.
Biasane paling cepet ing praktik amarga cache friendliness lan overhead rendah, lan iku in-place. Kasuwan paling parah O(n²) dihindari karo pivot randomized utawa median-of-three. Iku ora stabil.
Quicksort iku default ing akeh perpustakaan standar amarga kecepatan rata-rata sing apik lan panggunaan memori sing rendah.
Ngreti kenapa pilihan pivot nyebabke kasuwan paling parah O(n²) ngajari pelajaran penting: rata-rata lan kasuwan paling parah bisa nyimpang tajam.
Iku pancen topik wawancara sing digemari persis amarga kehalusan sing kuwi.