Sắp xếp nhanh (quick sort) trong Python
Chọn một chốt (pivot), chia list thành phần nhỏ hơn, bằng và lớn hơn, rồi sắp xếp từng phần theo cùng cách.
- Chọn chốt
- Phân hoạch bằng list comprehension
- Trung bình O(n log n), xấu nhất O(n²)
[7, 8, 1, 5]
- sắp xếp tiếp
[9]
- đã đúng chỗ
[10]
- một giá trị: xong
Phân hoạch quanh chốt
Vấn đề
Quicksort là một trong những ý tưởng sắp xếp được dùng nhiều nhất vì trung bình rất nhanh và dễ diễn đạt. Nó cho thấy một cách chia bài toán khác: không chia ở giữa mà chia quanh một giá trị được chọn.
Hình dung đời thường
Quicksort giống xếp sách theo chiều cao quanh một cuốn được chọn. Cuốn nào thấp hơn để sang chồng bên trái, cao hơn sang chồng bên phải, bằng chiều cao thì để ở giữa. Rồi xếp mỗi chồng hai bên theo cùng cách đó, và ghép các chồng lại.
pivot = values[len(values) // 2]📕 Chọn một cuốn để so sánhlower = [... if value < pivot]⬅️ Sách thấp hơn sang tráihigher = [... if value > pivot]➡️ Sách cao hơn sang phảiquick_sort(lower) + equal + quick_sort(higher)📚 Xếp từng bên rồi ghép các chồng lạiQuicksort chọn một phần tử chốt (pivot), chia các phần tử còn lại thành nhóm nhỏ hơn và lớn hơn nó, sắp xếp từng nhóm bằng đệ quy rồi ghép lại, với thời gian trung bình O(n log n).
Những điểm quan trọng
if len(values) <= 1:là trường hợp cơ sở: list như vậy đã có thứ tự.pivot = values[len(values) // 2]lấy giá trị ở giữa làm chốt.lower,equalvàhigherchia các giá trị quanh chốt;equalgiữ các giá trị trùng ở cùng một chỗ.quick_sort(lower) + equal + quick_sort(higher)sắp xếp hai bên rồi ghép ba list lại.
Khi nào nên sử dụng?
- Học phân hoạch (partition) và đệ quy.
- Sắp xếp tại chỗ đa dụng trong ngôn ngữ và thư viện (khi chọn chốt cẩn thận).
- Các bài toán chọn như tìm trung vị (quickselect dùng cùng cách phân hoạch).
Khi nào chưa cần
- Code Python thông thường:
sorted()nhanh hơn và giữ thứ tự ổn định. - Khi cần bảo đảm tốc độ cả trong trường hợp xấu nhất: chọn chốt tệ làm quicksort thành
O(n²), còn merge sort thì không bao giờ như vậy.
Mô phỏng Sắp xếp nhanh (quick sort) trong Python
O(n log n)Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.
Code ví dụ
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
Kết quả khi chạy
[1, 5, 7, 8, 9, 10]
Giải thích code
Phiên bản dễ đọc này chọn phần tử ở giữa làm pivot và tạo ba danh sách lower, equal và higher bằng list comprehension. Kết quả là ghép quick_sort(lower), equal và quick_sort(higher). Độ phức tạp trung bình là O(n log n), nhưng nếu pivot được chọn không tốt, thuật toán có thể chậm đến O(n²).
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Bỏ mất các giá trị bằng chốt
Nếu chỉ dùng < và >, các giá trị trùng với chốt sẽ biến mất.
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
Tất cả thử thách