Quicksort është algoritëm ndarje-dhe-sundimi që zgjedh një pivot, ndan elementet në ato më të vogla dhe më të mëdha se ai, pastaj rendit në mënyrë rekursive çdo anë. Rasti mesatar O(n log n), rasti më i keq O(n²).
Ndarja vendos pivot në pozicionin e tij përfundimtar të renditur; gjithçka majtas është më e vogël, gjithçka djathtas është më e madhe. Ndajmë në mënyrë rekursive të dyja anët.
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]
(Në praktikë përdoret ndarje në vend për të kursyer memorjen.)
| Rasti | Koha | Shkaku |
|---|---|---|
| Best/Average | O(n log n) | ndarje të balancuara |
| Worst | O(n²) | tashmë e renditur me pivot të keq |
Quicksort në vend përdor O(log n) hapësirë të stakut.
Zakonisht më i shpejti në praktikë për shkak të miqësimit të cache dhe përpyerjes të ulët, dhe është në vend. Rasti më i keq O(n²) shmangët me pivot të rastit ose mediana-prej-tre. Nuk është stabil.
Quicksort është përazgjedhje në shumë biblioteka standarde për shkak të shpejtësisë së shkëlqyer të rastit mesatar dhe përdorimit të ulët të memorjes.
Kuptimi se pse zgjedhja e pivot shkakton rastin më të keq O(n²) mëson një mësim kyç: rasti mesatar dhe më i keq mund të ndryshojnë ndjeshëm.
Është një temë e preferuar në intervista pikërisht për shkak të kësaj nianse.