Quicksort என்பது ஒரு பிரி-மற்றும்-வெற்றி வரிசைப்படுத்தல் வழிமுறை ஆகும், இது pivot ஐ தேர்ந்தெடுக்கிறது, உறுப்புகளை அதனை விட சிறியவை மற்றும் பெரியவை என பிரிக்கிறது, பின்னர் ஒவ்வொரு பக்கத்தையும் சுழல்நிலையாக வரிசைப்படுத்துகிறது. சராசரி O(n log n), மோசமான நிலை O(n²).
பிரிப்பது pivot ஐ அதன் இறுதி வரிசைப்படுத்தப்பட்ட நிலையில் வைக்கிறது; இடதுபுறத்தெல்லாம் சிறியவை, வலதுபுறத்தெல்லாம் பெரியவை. இரு பக்கங்களிலும் சுழல்நிலையாக செயல்படுத்துக.
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]
(நடைமுறையில் நினைவகத்தைச் சேமிக்க இடத்திலேயே பிரிப்பு பயன்படுத்தப்படுகிறது.)
| நிலை | நேரம் | காரணம் |
|---|---|---|
| Best/Average | O(n log n) | சமநிலைப்படுத்தப்பட்ட பிரிப்புகள் |
| Worst | O(n²) | ஏற்கனவே வரிசைப்படுத்தப்பட்ட மோசமான pivot உடன் |
இடத்திலேயே விரைவு வரிசைப்படுத்தல் O(log n) அடுக்கு இடத்தைப் பயன்படுத்துகிறது.
பொதுவாக நடைமுறையில் வேகமாக கேச-நட்பு மற்றும் குறைந்த மேல்நிலை காரணமாக, மற்றும் இடத்திலேயே உள்ளது. சீரற்ற அல்லது மூன்றின்-நடுநிலை pivot உடன் O(n²) மோசமான நிலை தவிர்க்கப்படுகிறது. நிலையல்ல.
விரைவு வரிசைப்படுத்தல் பல தரநிலை நூலகங்களில் இயல்புநிலை ஆகும், ஏனெனில் அதன் சிறந்த சராசரி-நிலை வேகம் மற்றும் குறைந்த நினைவக பயன்பாடு.
pivot தேர்வு O(n²) மோசமான நிலையை ஏன் ஏற்படுத்துகிறது என்பதைப் புரிந்துகொள்வது ஒரு முக்கிய பாடம் கற்பிக்கிறது: சராசரி மற்றும் மோசமான நிலை கூர்மையாக வேறுபடலாம்.
இந்த நுணுக்கமே காரணமாக இது நேர்காணல் பிரিய பিரிய கேள்வி.