Thuật toán & CTDL #05: Quick Sort - chọn chốt tệ là rơi thẳng về O(n²)
Quick Sort thường là thuật toán sắp xếp nhanh nhất trong thực tế, và toàn bộ nó dựa trên một mẹo: chọn một phần tử làm chốt (pivot), ném mọi số nhỏ hơn sang trái, rồi đặt chốt vào giữa. Nhưng câu hỏi phỏng vấn kinh điển nằm ở mặt tối của nó: đưa cho Quick Sort một mảng đã sắp sẵn, và nếu chọn chốt kiểu ngây thơ, nó chậm như Bubble Sort.
Ý tưởng
- Chọn một phần tử làm chốt. Bản đơn giản nhất (sơ đồ Lomuto): lấy phần tử cuối.
- Phân hoạch (partition): duyệt từ trái sang phải, giữ một "bức tường". Số nào nhỏ hơn chốt thì ném sang bên trái bức tường, và bức tường lùi sang phải một ô.
- Hết lượt, đặt chốt ngay sau bức tường. Lúc này mọi số bên trái nhỏ hơn chốt, mọi số bên phải lớn hơn hoặc bằng chốt. Chốt đã nằm đúng vị trí cuối cùng và đứng yên mãi mãi.
- Làm y hệt với nửa trái và nửa phải.
Khác với Merge Sort (chia dễ, trộn khó), Quick Sort làm hết việc nặng ở bước chia. Sau khi chia xong thì không cần trộn gì cả.
Chạy tay một ví dụ
Mảng trong video: [5, 2, 8, 1, 7, 3, 6, 4]. Chốt là số cuối: 4. Bức tường ban đầu ở trước ô đầu tiên.
| Xét | So với 4 | Hành động | Mảng |
|---|---|---|---|
| 5 | lớn hơn | bỏ qua | [5, 2, 8, 1, 7, 3, 6, 4] |
| 2 | nhỏ hơn | ném sang trái tường (đổi với 5) | [2, 5, 8, 1, 7, 3, 6, 4] |
| 8 | lớn hơn | bỏ qua | |
| 1 | nhỏ hơn | ném sang trái tường (đổi với 5) | [2, 1, 8, 5, 7, 3, 6, 4] |
| 7 | lớn hơn | bỏ qua | |
| 3 | nhỏ hơn | ném sang trái tường (đổi với 8) | [2, 1, 3, 5, 7, 8, 6, 4] |
| 6 | lớn hơn | bỏ qua |
Đặt chốt 4 ngay sau tường (đổi với 5): [2, 1, 3, 4, 7, 8, 6, 5]. Số 4 đã ở đúng vị trí thứ 4 và sẽ không bao giờ bị động tới nữa.
Tiếp tục với nửa trái [2, 1, 3] (chốt 3) và nửa phải [7, 8, 6, 5] (chốt 5). Mỗi lần chia, bài toán nhỏ lại, đến khi mỗi đoạn còn 0 hoặc 1 phần tử.
Code Python
import random
def quick_sort(a):
a = list(a)
_qs(a, 0, len(a) - 1)
return a
def _qs(a, lo, hi):
while lo < hi:
p = _partition(a, lo, hi)
# đệ quy nửa nhỏ hơn, lặp với nửa lớn hơn: stack tối đa O(log n)
if p - lo < hi - p:
_qs(a, lo, p - 1); lo = p + 1
else:
_qs(a, p + 1, hi); hi = p - 1
def _partition(a, lo, hi):
r = random.randint(lo, hi) # chốt ngẫu nhiên để tránh bẫy mảng đã sắp
a[r], a[hi] = a[hi], a[r]
pivot = a[hi]
wall = lo # mọi thứ bên trái wall đều < pivot
for j in range(lo, hi):
if a[j] < pivot:
a[wall], a[j] = a[j], a[wall]
wall += 1
a[wall], a[hi] = a[hi], a[wall] # đặt chốt ngay sau bức tường
return wall
print(quick_sort([5, 2, 8, 1, 7, 3, 6, 4])) # [1, 2, 3, 4, 5, 6, 7, 8]
print(quick_sort(range(5000)) == list(range(5000))) # True, mảng đã sắp vẫn ổn
Bỏ dòng random.randint (luôn lấy số cuối làm chốt) và đổi _qs thành đệ quy cả hai nhánh, bạn sẽ có đúng bản trong video. Chạy bản đó với range(5000) trên Python sẽ gặp RecursionError, vì độ sâu đệ quy lên tới khoảng 5000 tầng, vượt giới hạn mặc định 1000.
Độ phức tạp
- Trung bình: O(n log n). Chốt chia mảng thành hai phần không quá lệch, nên có khoảng log n tầng, mỗi tầng O(n).
- Tệ nhất: O(n²). Xảy ra khi chốt luôn là phần tử nhỏ nhất hoặc lớn nhất, ví dụ lấy phần tử cuối trên mảng đã sắp sẵn (hoặc sắp ngược). Mỗi lần chia chỉ bớt được đúng một phần tử: n-1 + n-2 + ... + 1 = n(n-1)/2 phép so sánh, y như Bubble Sort.
- Tốt nhất: O(n log n), khi chốt luôn chia đôi đều.
- Bộ nhớ: in-place, nhưng stack đệ quy tốn O(log n) trung bình. Bản ngây thơ có thể tốn O(n) stack ở trường hợp tệ nhất. Mẹo "đệ quy nửa nhỏ, lặp nửa lớn" như code trên giới hạn stack ở O(log n) trong mọi trường hợp.
- Stable: không. Phép đổi chỗ đường dài có thể đảo thứ tự hai phần tử bằng nhau.
Vì sao thực tế lại nhanh?
Cùng O(n log n) với Merge Sort, nhưng Quick Sort thường nhanh hơn vì: phân hoạch tại chỗ, không cấp phát mảng phụ, quét bộ nhớ tuần tự nên rất hợp cache, và vòng lặp trong rất gọn.
Tránh bẫy O(n²)
- Chốt ngẫu nhiên: không có input cố định nào luôn gây ra trường hợp tệ. Xác suất rơi vào O(n²) cực kỳ nhỏ.
- Median-of-three: lấy trung vị của phần tử đầu, giữa, cuối. Xử lý tốt mảng đã sắp.
- Phân hoạch 3 đường (Dutch National Flag): tách thành
< chốt,= chốt,> chốt. Cần thiết khi có nhiều phần tử trùng nhau. Mảng toàn số giống nhau với Lomuto cũng rơi về O(n²). - Introsort: chạy Quick Sort, nếu đệ quy quá sâu (khoảng 2 log n tầng) thì chuyển sang Heap Sort, đoạn nhỏ thì dùng Insertion Sort. Đây là cách nhiều bản cài đặt
std::sortcủa C++ làm, đảm bảo O(n log n) tệ nhất.
Khi nào dùng, khi nào không
Dùng khi cần sắp mảng trong bộ nhớ nhanh, không cần stable, và bộ nhớ phụ hạn chế. Nhiều thư viện dùng biến thể của nó, ví dụ Java dùng Dual-Pivot Quicksort cho mảng kiểu nguyên thủy.
Không dùng khi cần stable (chọn Merge Sort/Timsort), khi cần đảm bảo cứng thời gian tệ nhất mà không có cơ chế như introsort, hoặc với linked list.
Câu hỏi phỏng vấn hay gặp
- Trường hợp tệ nhất của Quick Sort là gì, xảy ra khi nào? O(n²), khi chốt luôn là min hoặc max, ví dụ lấy phần tử cuối trên mảng đã sắp. Nhiều người trả lời sai là "mảng ngẫu nhiên".
- Cách tránh? Chốt ngẫu nhiên, median-of-three, introsort.
- Quick Sort có stable không? Không.
- Tìm phần tử lớn thứ k? Quickselect: chỉ đệ quy vào nửa chứa k, trung bình O(n).
Lời kết
Quick Sort là ví dụ điển hình cho việc độ phức tạp trung bình và tệ nhất có thể khác nhau một trời một vực, và một quyết định nhỏ như chọn chốt quyết định tất cả.
Đây là bài 05/19 của series "Thuật toán & Cấu trúc dữ liệu - Giải thuật". Bản video ngắn có hoạt hình minh họa chốt, bức tường và từng lần ném số sang trái nằm trên page Trà Đá Tech: https://www.facebook.com/profile.php?id=61596642752252
Bạn sẽ chọn chốt thế nào để tránh bẫy? Hãy chia sẻ trong phần bình luận.
Nếu thấy bài viết hữu ích, hãy upvote và follow để theo dõi các bài tiếp theo.
Bài tiếp theo: Binary Search - tìm 1 phần tử trong 1 tỷ chỉ với 30 bước
All rights reserved