Sắp xếp nhanh (quick sort) trong Python
Bài 18/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 9 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 12
Sắp xếp nhanh (quick sort) là thuật toán sắp xếp chọn một phần tử làm chốt, chia dãy thành phía nhỏ hơn và phía lớn hơn chốt, rồi xếp từng phía bằng đệ quy. Với dữ liệu lộn xộn nó thường chạy nhanh hơn các cách tự viết khác, ví dụ khi xếp các trạm xe theo số khách lên xe trong ngày.
Cần biết trước: list comprehension, đệ quy và sắp xếp trộn.
Chọn chốt và chia dãy thành ba phía
Chốt (pivot) là phần tử dùng làm mốc để so. Bài này lấy phần tử ở giữa list, ds[len(ds) // 2]. Ba list comprehension có điều kiện lọc chia list ra phần nhỏ hơn chốt, phần bằng chốt và phần lớn hơn chốt. Danh sách dưới đây là số khách lên xe ở bảy trạm của một tuyến:
khach = [14, 3, 22, 9, 30, 9, 5]
chot = khach[len(khach) // 2]
nho = [x for x in khach if x < chot]
bang = [x for x in khach if x == chot]
lon = [x for x in khach if x > chot]
print("Chốt:", chot)
print(nho, bang, lon)KẾT QUẢ
Chốt: 9
[3, 5] [9, 9] [14, 22, 30]Sau một lần chia, list bang đã đứng đúng chỗ của nó: mọi số bên trái nhỏ hơn 9, mọi số bên phải lớn hơn. Hai phía nho và lon chưa xếp, nhưng mỗi phía ngắn hơn list ban đầu. Việc chia một dãy quanh chốt như vậy gọi là phân hoạch.
Đệ quy hai phía
Merge sort chia đôi trước và làm việc chính lúc trộn. Quick sort làm ngược lại: việc chính nằm ở bước phân hoạch, còn bước ghép chỉ là nối ba list. Lời gọi dừng khi list còn nhiều nhất một phần tử, vì không còn gì để phân hoạch. Hàm dưới đây in chốt của mỗi lời gọi, thụt vào theo độ sâu:
def quick_sort(ds, tang=0):
if len(ds) <= 1:
return ds
chot = ds[len(ds) // 2]
print(" " * tang + "chốt", chot, "trong", ds)
nho = [x for x in ds if x < chot]
bang = [x for x in ds if x == chot]
lon = [x for x in ds if x > chot]
sau = tang + 1
return quick_sort(nho, sau) + bang + quick_sort(lon, sau)
print(quick_sort([14, 3, 22, 9, 30, 9, 5]))KẾT QUẢ
chốt 9 trong [14, 3, 22, 9, 30, 9, 5]
chốt 5 trong [3, 5]
chốt 22 trong [14, 22, 30]
[3, 5, 9, 9, 14, 22, 30]Chỉ ba lời gọi chọn chốt, vì các list [3], [14], [30] chạm điều kiện dừng. Đổi ds[len(ds) // 2] thành ds[0] rồi chạy lại: dòng đầu in chốt 14 trong [14, 3, 22, 9, 30, 9, 5] và cây chia sâu thêm một tầng. Chốt khác nhau cho cùng một kết quả, nhưng số lời gọi thay đổi.
Khi nào sắp xếp nhanh chạy chậm
Mỗi lời gọi so cả list với chốt. Nếu chốt chia list thành hai phía gần bằng nhau, có khoảng log₂(n) tầng và tổng cộng O(n log n) phép so, như merge sort. Nếu chốt là phần tử nhỏ nhất hay lớn nhất, một phía rỗng và phía kia chỉ ngắn hơn một phần tử. Hàm dưới đây đếm tổng số phần tử phải so với chốt qua mọi lời gọi, với một list đã xếp sẵn:
def so_phep_so(ds, chon):
if len(ds) <= 1:
return 0
chot = chon(ds)
nho = [x for x in ds if x < chot]
lon = [x for x in ds if x > chot]
return len(ds) + so_phep_so(nho, chon) + so_phep_so(lon, chon)
da_xep = list(range(200))
print("Chốt đầu:", so_phep_so(da_xep, lambda ds: ds[0]))
print("Chốt giữa:", so_phep_so(da_xep, lambda ds: ds[len(ds) // 2]))KẾT QUẢ
Chốt đầu: 20099
Chốt giữa: 1280Lấy phần tử đầu làm chốt với list đã xếp, mỗi tầng chỉ bớt một phần tử, nên có tới 199 tầng và khoảng n²/2 phép so: trường hợp xấu nhất O(n²). Với list dài vài nghìn phần tử đã xếp, số tầng vượt giới hạn gọi lồng nhau của Python và hàm báo RecursionError. Chốt ở giữa tránh được list đã xếp, nhưng vẫn có những list khiến nó chọn kém. Bài Big O giải thích cách đọc O(n²) và O(n log n).
Ổn định hay không: hai cách phân hoạch
Ba list comprehension giữ nguyên thứ tự các phần tử trong mỗi phía, nên cách chia ra list mới là ổn định. Xếp các trạm (ten, so_khach) theo số khách:
def xep_theo_khach(ds):
if len(ds) <= 1:
return ds
chot = ds[len(ds) // 2][1]
nho = [t for t in ds if t[1] < chot]
bang = [t for t in ds if t[1] == chot]
lon = [t for t in ds if t[1] > chot]
return xep_theo_khach(nho) + bang + xep_theo_khach(lon)
cac_tram = [("T1", 9), ("T2", 14), ("T3", 3), ("T4", 9), ("T5", 6)]
print(xep_theo_khach(cac_tram))KẾT QUẢ
[('T3', 3), ('T5', 6), ('T1', 9), ('T4', 9), ('T2', 14)]Trạm T1 đứng trước T4 trong list gốc và vẫn đứng trước sau khi xếp. Cách này tạo list mới ở mỗi lời gọi nên tốn thêm bộ nhớ. Nhiều bản quick sort phân hoạch tại chỗ: con trỏ j đi qua đoạn đang xếp, con trỏ i đánh dấu chỗ đặt phần tử nhỏ hơn chốt tiếp theo, và chốt là phần tử cuối đoạn:
def quick_sort(ds, dau, cuoi):
if dau >= cuoi:
return
chot, i = ds[cuoi][1], dau
for j in range(dau, cuoi):
if ds[j][1] < chot:
ds[i], ds[j] = ds[j], ds[i]
i += 1
ds[i], ds[cuoi] = ds[cuoi], ds[i]
quick_sort(ds, dau, i - 1)
quick_sort(ds, i + 1, cuoi)
cac_tram = [("T1", 9), ("T2", 14), ("T3", 3), ("T4", 9), ("T5", 6)]
quick_sort(cac_tram, 0, len(cac_tram) - 1)
print(cac_tram)KẾT QUẢ
[('T3', 3), ('T5', 6), ('T4', 9), ('T1', 9), ('T2', 14)]Bản tại chỗ không tạo list mới, nhưng các phép đổi chỗ đưa T4 lên trước T1: phân hoạch tại chỗ không ổn định. Khi cần thứ tự cũ của các phần tử bằng nhau, hãy dùng bản chia ra list mới hoặc merge sort.
Kiểm tra nhanh
Chia
[20, 4, 17, 11, 4, 25]bằng chốtds[len(ds) // 2]như bài. Ba listnho,bang,lonlà gì?[4, 4],[17],[20, 25][4, 4],[11],[17, 20, 25][4, 4],[11],[20, 17, 25]
Những điều nào đúng với quick sort của bài?
- Lấy phần tử đầu làm chốt với list đã xếp tốn khoảng n²/2 phép so
- Mọi cách chọn chốt đều cho O(n log n)
- Phân hoạch tại chỗ giữ thứ tự cũ của phần tử bằng nhau
- Bản chia ra ba list mới bằng list comprehension là ổn định
Bỏ list
bang, ghépquick_sort(nho) + [chot] + quick_sort(lon). Gọi với[4, 4, 1, 4]thì trả về gì?[1, 4][1, 4, 4, 4][4, 1]
Dùng
nho = [x for x in ds if x <= chot]và ghépquick_sort(nho) + quick_sort(lon). Gọiquick_sort([3, 8])thì sao?- Trả về
[3, 8] - Trả về
[8, 3] - Báo lỗi RecursionError
- Trả về
Bài tập
Xếp các trạm theo số khách và ghi lại dãy chốt
Mỗi số trong ds là số khách lên xe ở một trạm. Viết thân hàm quick_sort_chot(ds) xếp tăng dần bằng quick sort và ghi lại các chốt đã chọn. List có từ hai phần tử thì lấy chốt ds[len(ds) // 2], chia ra ba list nhỏ hơn, bằng và lớn hơn chốt, rồi xếp phía nhỏ trước, phía lớn sau bằng đệ quy. Dãy chốt gồm chốt của lời gọi hiện tại, tiếp theo là dãy chốt của phía nhỏ, rồi của phía lớn. List rỗng hay một phần tử không chọn chốt. Không dùng sorted() hay sort(), và không sửa ds.
Ví dụ: quick_sort_chot([41, 7, 23, 7, 58, 12]) trả về ([7, 7, 12, 23, 41, 58], [7, 58, 23]).
Trả về: list đã xếp và list các chốt theo thứ tự đã chọn, một tuple.
def quick_sort_chot(ds):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Quick sort chọn một chốt, chia list thành phần nhỏ hơn, bằng và lớn hơn chốt, rồi xếp hai phía bằng đệ quy.
Bài lấy chốt ở giữa,
ds[len(ds) // 2], và chia bằng ba list comprehension.Phải giữ list
bang: bỏ nó thì mất phần tử trùng, gộp nó vào phía nhỏ thì có thể đệ quy mãi.Chốt chia đều cho O(n log n); chốt luôn là số nhỏ nhất hay lớn nhất cho O(n²).
Bản chia ra list mới ổn định nhưng tốn bộ nhớ; bản phân hoạch tại chỗ đổi chỗ trong list và không ổn định.
Câu hỏi thường gặp
Sắp xếp nhanh (quick sort) là gì và vì sao lại gọi là nhanh?
Đó là thuật toán chia để trị: chọn chốt, phân hoạch, rồi đệ quy hai phía. Trên dữ liệu lộn xộn, bản tại chỗ chỉ đổi chỗ trong cùng một list và đi qua bộ nhớ liền nhau. Vì vậy nó thường chạy nhanh hơn các thuật toán O(n log n) khác, dù trường hợp xấu nhất là O(n²).
Nên chọn phần tử chốt như thế nào?
Phần tử đầu hay cuối dễ viết nhưng chậm với list đã xếp. Phần tử giữa tránh được trường hợp đó. Một cách phổ biến khác là chọn ngẫu nhiên bằng module random, khiến không có list cố định nào luôn gây chậm.
Có nên tự viết quick sort để sắp xếp trong chương trình Python thật không?
Thường là không. sorted() và sort() dùng Timsort, ổn định, viết bằng C và luôn giữ O(n log n), nên chạy nhanh hơn hàm tự viết. Bài thuật toán sắp xếp so sánh Timsort với các thuật toán của nhóm này.
Sắp xếp nhanh khác merge sort ở điểm nào?
Merge sort chia đôi đúng giữa và làm việc chính lúc trộn, nên luôn O(n log n) và ổn định. Quick sort làm việc chính lúc phân hoạch, cách chia phụ thuộc chốt, và bản tại chỗ không cần thêm list mới.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.