Quicksort shine divide-and-conquer sort da ke zabar pivot, sanya abubuwa zuwa waɗanda suke ƙarami da mafi girma fiye da shi, sannan ake maimaita ake tsara kowane gida. Average O(n log n), mafi muni case O(n²).
Partitioning yana saka pivot a cikin matsayin da aka tsara a gida; komai hagu yana ƙarami, komai dama yana girma. Maimaita akan bangarorin biyu.
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]
(In-place partitioning ana amfani da shi a aiki don adana ƙarfin ajiya.)
| Case | Lokaci | Dalilin |
|---|---|---|
| Best/Average | O(n log n) | daidaitaccen partitions |
| Worst | O(n²) | da aka tsara jiya tare da badi pivot |
In-place quicksort yana amfani da O(log n) stack space.
Yawanci mafi sauri a aiki saboda nawa ake abin da cache kasa da mababbar ajiya, kuma yana in-place. Mafi muni O(n²) case ana gudu shi tare da randomized ko median-of-three pivot. Bai daidai ba.
Quicksort shine default a yawancin standard libraries saboda kyakkyawan sauri na average-case da mababbar ajiya.
Samun fahimta dalilin da pivot zabin ke sabawa O(n²) mafi muni case yana koyar abin muhimmanci: average da mafi muni case zasu iya rabu da kyar.
Gari ne gida na tattaun interview saboda abin da gida shi ke ne.
Ɗakin karatu na tambayoyin hira na IT tare da amsoshi cikakke — daga Junior zuwa Senior.
Ba da Gudummawa