Quicksort არის "გაყოფა და დამორჩილება" დალაგება, რომელიც ირჩევს საყრდენ წერტილს, ყოფს ელემენტებს მცირე და დიდ ელემენტებად, შემდეგ რეკურსიულად ალაგებს თითოეულ მხარეს. საშუალო O(n log n), ყველაზე ძTV შემთხვევა O(n²).
დანაყოფი საყრდენ წერტილს მის საბოლოო დალაგებულ ადგილას აყენებს; ყველაფერი მარცხნივ უფრო მცირეა, ყველაფერი მარჯვნივ უფრო დიდია. რეკურსია ორივე მხარეს.
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 დანაყოფი გამოიყენება პრაქტიკაში მეხსიერების დასაზოგად.)
| შემთხვევა | დრო | მიზეზი |
|---|---|---|
| საუკეთესო/საშუალო | O(n log n) | დაბალანსებული დანაყოფი |
| ყველაზე ძTV | O(n²) | უკვე დალაგებული ცუდი საყრდენით |
In-place quicksort იყენებს O(log n) სტეკის სივრცეს.
ჩვეულებრივ ყველაზე სწრაფი პრაქტიკაში კეშ-მეგობრული და დაბალი ხარჯის გამო, და ის in-place არის. O(n²) ყველაზე ძTV შემთხვევა თავს ირიდება შემთხვევითი ან მედიანა-სამი საყრდენით. ის არ არის სტაბილური.
Quicksort არის ნაგულისხმევი ბევრი სტანდარტული ბიბლიოთეკაში, რადგან მას აქვს შესანიშნავი საშუალო შემთხვევის სიჩქარე და დაბალი მეხსიერების გამოყენება.
იმის გაგება, რატომ იწვევს საყრდენ წერტილის არჩევანი O(n²) ყველაზე ძTV შემთხვევას, ასწავლის მნიშვნელოვან გაკვეთილს: საშუალო და ყველაზე ძTV შემთხვევა შეიძლება მკვეთრად განსხვავდებოდეს.
ეს არის საჭირო ინტერვიუს თემა ზუსტად ამ დახვეწილობის გამო.