Quicksort hija algoritmu ta' dividi-u-rregina li tagħżel pivot, taqsam l-elementi fi dawk iżgħar u akbar minnu, imbagħad tirranġa r-rikorsivement kull naħa. Medja O(n log n), każ agħar O(n²).
Il-qsim ipoġġi l-pivot fil-pożizzjoni finali miċ-ċaqla; kollox fuq ix-xellug huwa iżgħar, kollox fuq il-lemin huwa akbar. Rikorsjoni fuq it-tnejn tal-ġnub.
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]
(Il-qsim in-place jintuża fil-prattika biex issalva l-memorja.)
| Każ | Ħin | Ċaġun |
|---|---|---|
| Aħjar/Medja | O(n log n) | qsim bilanċjat |
| Agħar | O(n²) | diġà miċ-ċaqal b'pivot ħażin |
Quicksort in-place juża O(log n) spazju tal-istakk.
Normalment l-aktar veloċi fil-prattika minħabba l-amsħar cache-friendly u overhead baxxa, u hija in-place. Il-każ agħar O(n²) jiġi evitat b'pivot random jew medjan-ta'-tlieta. Hija mhux stabbli.
Quicksort hija l-default f'ħafna libreriji standard minħabba l-veloċità medja eċċellenti u l-użu baxxa tal-memorja.
Il-fahim għaliex l-għażla tal-pivot tikkawża l-każ agħar O(n²) jgħallmu lezzjoni kruċjali: il-każ medju u l-każ agħar jistgħu jiddivergew b'mod qawwi.
Hi suġġett preferut ta' intervista preċisament minħabba dik is-subtilezza.