Thuật toán Python

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.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • 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²)
Chốt 9 (giá trị ở giữa) trong [10, 7, 8, 9, 1, 5]
lower
[7, 8, 1, 5]
  • sắp xếp tiếp
equal
[9]
  • đã đúng chỗ
higher
[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.

Từ những chồng sách đến code
pivot = values[len(values) // 2]📕 Chọn một cuốn để so sánh
lower = [... if value < pivot]⬅️ Sách thấp hơn sang trái
higher = [... if value > pivot]➡️ Sách cao hơn sang phải
quick_sort(lower) + equal + quick_sort(higher)📚 Xếp từng bên rồi ghép các chồng lại
Phân hoạch quanh một chốt (pivot), rồi xếp mỗi bên theo cùng cách.
Định nghĩa ngắn gọn

Quicksort 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

  1. if len(values) <= 1: là trường hợp cơ sở: list như vậy đã có thứ tự.
  2. pivot = values[len(values) // 2] lấy giá trị ở giữa làm chốt.
  3. lower, equal và higher chia các giá trị quanh chốt; equal giữ các giá trị trùng ở cùng một chỗ.
  4. 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ụ

Chạy code →
main.py
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]))
Lấy nút Run cho ví dụ này

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.

  1. 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.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đ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.
Chạy trong trình biên dịch Python →

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.

Sai
return quick_sort(lower) + [pivot] + quick_sort(higher)
Cách sửa
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