Quicksort ni algoriti ya gawanya-na-kushinda inayochagua pivot, inagawanya elementi katika vile vilivyokua vidogo na vikubwa kuliko hiyo, kisha inakamatia kila upande. Kawaida O(n log n), kesi mbaya zaidi O(n²).
Kugawanya kunaweka pivot katika nafasi yake ya mwisho iliyokamatia; kila kitu upande wa kushoto ni kidogo, kila kitu upande wa kulia ni kikubwa. Kamatia kila upande.
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]
(Kugawanya mahali (in-place) linatumika katika mazoezi kuokoa kumbukumbu.)
| Kesi | Wakati | Sababu |
|---|---|---|
| Best/Average | O(n log n) | kupatanisha kugawanya |
| Worst | O(n²) | iliyokamatia tayari na pivot mbaya |
Quicksort ya mahali inatumia O(log n) nafasi ya stack.
Kawaida ni ya haraka zaidi katika mazoezi kwa sababu ya ukaribishaji wa cache na upitaji wa chini, na ni mahali. Kesi mbaya O(n²) inazuiwa kwa pivot ya bahati nasibu au wastani-wa-tatu. Si imara.
Quicksort ni chaguo-msingi katika maktaba nyingi za kawaida kwa sababu ya kasi ya kesi ya kawaida na upitaji wa chini wa kumbukumbu.
Kuelewa kwa nini chaguo la pivot linalosababisha kesi mbaya O(n²) kunafunda somo muhimu: kesi ya kawaida na ya mwisho inaweza kutofautiana sana.
Ni mada ya pencil katika mahojiano kwa sababu tu ya nuance hii.