Quicksort είναι ένας αλγόριθμος ταξινόμησης divide-and-conquer που επιλέγει ένα 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]
(Η διαμέριση σε place (in-place) χρησιμοποιείται στην πράξη για αποταμίευση μνήμης.)
| Περίπτωση | Χρόνος | Αιτία |
|---|---|---|
| Καλύτερο/Μέσο | O(n log n) | ισορροπημένες διαμερίσεις |
| Χειρότερο | O(n²) | ήδη ταξινομημένο με κακό pivot |
Το in-place quicksort χρησιμοποιεί O(log n) χώρο στοίβας.
Συνήθως το ταχύτερο στην πράξη λόγω της φιλικότητας προς την cache και του χαμηλού overhead, και είναι in-place. Η χειρότερη περίπτωση O(n²) αποφεύγεται με ένα τυχαιοποιημένο ή median-of-three pivot. Δεν είναι σταθερό.
Το Quicksort είναι το προεπιλεγμένο σε πολλές τυπικές βιβλιοθήκες λόγω της εξαιρετικής μέσης ταχύτητας και της χαμηλής χρήσης μνήμης.
Η κατανόηση του λόγου για τον οποίο η επιλογή pivot προκαλεί την χειρότερη περίπτωση O(n²) διδάσκει ένα σημαντικό μάθημα: ο μέσος όρος και η χειρότερη περίπτωση μπορούν να αποκλίνουν απότομα.
Είναι ένα αγαπητό θέμα συνέντευξης ακριβώς λόγω αυτής της λεπτομέρειας.