Quicksort là một thuật toán sắp xếp theo divide-and-conquer, chọn một pivot (chốt), phân hoạch các phần tử thành nhóm nhỏ hơn và nhóm lớn hơn nó, rồi sắp xếp đệ quy mỗi bên. Trung bình O(n log n), xấu nhất O(n²).
Việc phân hoạch đặt pivot vào vị trí đã sắp xếp cuối cùng của nó; tất cả bên trái nhỏ hơn, tất cả bên phải lớn hơn. Đệ quy trên cả hai bên.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # chọn một pivot
left = [x for x in arr if x < pivot] # nhỏ hơn
mid = [x for x in arr if x == pivot] # bằng
right = [x for x in arr if x > pivot] # lớn hơn
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(Trong thực tế, phân hoạch tại chỗ được dùng để tiết kiệm bộ nhớ.)
| Trường hợp | Thời gian | Nguyên nhân |
|---|---|---|
| Tốt/Trung bình | O(n log n) | phân hoạch cân bằng |
| Xấu nhất | O(n²) | đã sắp xếp với pivot kém |
Quicksort tại chỗ dùng O(log n) bộ nhớ stack.
Thường là nhanh nhất trong thực tế nhờ thân thiện với cache và chi phí thấp, và nó là tại chỗ. Trường hợp xấu nhất O(n²) được tránh bằng pivot ngẫu nhiên hoặc median-of-three. Nó không ổn định.
Quicksort là mặc định trong nhiều thư viện chuẩn nhờ tốc độ trung bình xuất sắc và mức dùng bộ nhớ thấp.
Hiểu được vì sao việc chọn pivot gây ra trường hợp xấu nhất O(n²) dạy một bài học then chốt: trường hợp trung bình và xấu nhất có thể chênh lệch rất lớn.
Đây là một chủ đề phỏng vấn được ưa thích chính vì sắc thái đó.