Bỏ qua đến nội dung chính
Mục lục

Thuật toán sắp xếp trong Python: bảng so sánh và cách chọn

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 13/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

Thuật toán sắp xếp là cách đưa các phần tử của một list về đúng thứ tự. Các thuật toán khác nhau ở số phép so sánh, bộ nhớ dùng thêm và việc có giữ thứ tự cũ của các phần tử bằng nhau hay không. Trang này đặt bảy thuật toán hay gặp cạnh nhau trong một bảng, đo số phép so sánh của sort() mà Python dùng, rồi chỉ cách chọn thuật toán cho từng việc.

Cần biết trước: sắp xếp list, Big O và lambda.

Bảng so sánh bảy thuật toán sắp xếp

Mỗi dòng của bảng có một bài riêng, mô phỏng thuật toán từng bước và đếm số bước của nó. Ở đây n là số phần tử, k là khoảng giá trị (giá trị lớn nhất trừ nhỏ nhất, cộng một), d là số chữ số của số lớn nhất.

Thuật toán

Tốt nhất

Trung bình

Xấu nhất

Bộ nhớ thêm

Ổn định

Tại chỗ

Bubble sort

O(n)

O(n²)

O(n²)

O(1)

Có

Có

Selection sort

O(n²)

O(n²)

O(n²)

O(1)

Không

Có

Insertion sort

O(n)

O(n²)

O(n²)

O(1)

Có

Có

Merge sort

O(n log n)

O(n log n)

O(n log n)

O(n)

Có

Không

Quick sort, tại chỗ

O(n log n)

O(n log n)

O(n²)

O(log n)

Không

Có

Counting sort

O(n + k)

O(n + k)

O(n + k)

O(n + k)

Có

Không

Radix sort

O(d · n)

O(d · n)

O(d · n)

O(n)

Có

Không

Timsort (sort() của Python)

O(n)

O(n log n)

O(n log n)

O(n)

Có

Không: sửa chính list nhưng cần O(n) bộ nhớ tạm

Ba thuật toán đầu đơn giản, chỉ đổi chỗ các phần tử ngay trong list, nhưng tốn O(n²). Merge sort và quick sort chia list thành phần nhỏ, nên chỉ tốn khoảng O(n log n). Counting sort và radix sort không so sánh hai phần tử với nhau, mà đếm theo giá trị. Counting sort chỉ hợp với số nguyên trong một khoảng không quá rộng, còn radix sort hợp với số nguyên có ít chữ số. Cột "Tốt nhất" của bubble sort giả định bản có dừng sớm khi một lượt không đổi chỗ nào. Dòng quick sort là bản phân hoạch tại chỗ: bản chia ra list mới thì ổn định nhưng tốn O(n) bộ nhớ.

O(n²) và O(n log n) khác nhau tới đâu

Hai cột độ phức tạp nghe gần nhau, nhưng khác biệt lớn dần theo n. Đoạn dưới tính hai con số, dùng n.bit_length(), số chữ số nhị phân của n, thay cho log₂ n.

python
for n in [10, 1000, 1_000_000]:
    n_binh_phuong = n * n
    n_log_n = n * n.bit_length()
    print(n, n_binh_phuong, n_log_n, n_binh_phuong // n_log_n)

KẾT QUẢ

10 100 40 2
1000 1000000 10000 100
1000000 1000000000000 20000000 50000

Với 10 phần tử, hai cách gần như ngang nhau. Với một triệu phần tử, O(n²) tốn gấp khoảng năm mươi nghìn lần. Đổi [10, 1000, 1_000_000] thành [10, 100] rồi chạy lại: dòng cuối in 100 10000 700 14.

Đếm số phép so sánh của sort()

sort() và sorted() của Python dùng Timsort, do Tim Peters viết lại cho Python 2.3 (ra mắt 29/07/2003, theo trang What's New in Python 2.3). Muốn đếm số phép so sánh của nó, bạn bọc mỗi khóa trong một object biết tự đếm: lớp So giữ giá trị trong self.v và định nghĩa __lt__, phép so sánh mà sắp xếp gọi (xem so sánh và sắp xếp object).

python
dem = [0]
class So:
    def __init__(self, v):
        self.v = v
    def __lt__(self, khac):
        dem[0] += 1
        return self.v < khac.v
def so_lan_so(ds):
    dem[0] = 0
    sorted(ds, key=So)
    return dem[0]
lon_xon = sorted(range(1000), key=lambda i: i * 7919 % 1000)
print(so_lan_so(range(1000)), so_lan_so(range(1000, 0, -1)))
print(round(so_lan_so(lon_xon), -2))

KẾT QUẢ

999 999
8600

List 1000 số đã xếp sẵn chỉ cần 999 phép so sánh, đúng n - 1: Timsort đi một lượt, thấy cả list là một đoạn tăng dần và dừng. List xếp ngược cũng vậy, vì Timsort nhận ra đoạn giảm dần và lật nó lại. List lộn xộn cần khoảng 8.600 phép so sánh, gần với n log₂ n là khoảng 10.000. Selection sort luôn so n(n - 1)/2 lần, tức 499.500 lần với 1000 phần tử. Con số đúng của list lộn xộn lệch vài lần giữa các bản Python, nên đoạn code làm tròn tới hàng trăm.

Timsort chia list thành các đoạn đã có thứ tự sẵn, gọi là run. Đoạn quá ngắn được nối dài bằng insertion sort, rồi các đoạn được trộn với nhau như merge sort. Dữ liệu thật thường có nhiều đoạn đã xếp, như lịch sử thao tác ghi theo giờ, nên Timsort hay nhanh hơn mức O(n log n). Từ Python 3.11, CPython đổi cách chọn hai đoạn để trộn sang powersort (changelog Python 3.11.0a1, bpo-34561), còn ý tưởng chia theo đoạn vẫn giữ nguyên.

Sắp xếp ổn định và sắp xếp tại chỗ

Sắp xếp ổn định giữ nguyên thứ tự cũ của các phần tử có khóa bằng nhau. Tính chất này cho bạn xếp theo nhiều khóa: xếp theo khóa phụ trước, rồi xếp theo khóa chính, các phần tử cùng khóa chính vẫn giữ thứ tự theo khóa phụ.

python
hang_cho = [("K03", "VIP", 25), ("K11", "Thường", 40),
            ("K07", "VIP", 12), ("K20", "Thường", 18)]
hang_cho.sort(key=lambda khach: khach[2])
hang_cho.sort(key=lambda khach: khach[1])
for khach in hang_cho:
    print(khach)

KẾT QUẢ

('K20', 'Thường', 18)
('K11', 'Thường', 40)
('K07', 'VIP', 12)
('K03', 'VIP', 25)

Hai khách nhóm Thường đứng trước, theo thứ tự 18 rồi 40 phút, sau đó là hai khách VIP. Bạn cũng có thể xếp một lần với khóa là một bộ, key=lambda khach: (khach[1], khach[2]), vì Python so bộ theo từng phần tử từ trái sang phải.

Sắp xếp tại chỗ thay đổi chính list ban đầu và chỉ dùng thêm một lượng bộ nhớ không đổi, như selection sort chỉ cần vài biến. list.sort() sửa chính list, nhưng Timsort cần thêm một vùng nhớ tạm tới khoảng nửa list khi trộn, nên theo nghĩa này nó không tại chỗ. sorted() luôn tạo list mới, nên tốn thêm bộ nhớ bằng cả list.

Chọn thuật toán sắp xếp nào khi nào

Trong code Python hằng ngày, câu trả lời gần như luôn là sort() hay sorted(): ổn định, viết bằng C, và nhanh với dữ liệu đã gần có thứ tự. Các thuật toán khác vẫn đáng học vì những lý do sau.

  • Phỏng vấn và bài thi hay yêu cầu tự viết, giải thích, đếm số bước của một thuật toán.

  • Insertion sort rất nhanh với list ngắn hay gần như đã xếp, đó là lý do Timsort dùng nó cho các đoạn ngắn.

  • Counting sort và radix sort thắng về số bước khi giá trị là số nguyên trong khoảng hẹp, như điểm từ 0 tới 10.

  • Selection sort đổi chỗ ít nhất, tối đa n - 1 lần, có ích khi mỗi lần ghi rất tốn.

Kiểm tra nhanh

  1. Với hàm so_lan_so() của bài, so_lan_so(range(5)) trả về gì?

    • 0
    • 10
    • 4
  2. Muốn xếp hàng chờ theo nhóm khách, trong mỗi nhóm theo số phút chờ, những cách nào đúng?

    • sort() theo số phút, rồi sort() theo nhóm
    • sort() theo nhóm, rồi sort() theo số phút
    • Một lần sort(key=lambda khach: (khach[1], khach[2]))
    • Một lần sort(key=lambda khach: khach[1])
  3. Theo bảng của bài, thuật toán nào vẫn tốn O(n²) ngay cả khi list đã xếp sẵn?

    • Insertion sort
    • Selection sort
    • Bubble sort có dừng sớm
  4. Theo bảng của bài, những câu nào đúng?

    • Merge sort xếp tại chỗ
    • Quick sort phân hoạch tại chỗ không ổn định
    • Selection sort xếp tại chỗ, chỉ dùng O(1) bộ nhớ thêm
    • Counting sort không ổn định
Đúng hết lần đầu +15 XP

Bài tập

Biến một cách xếp thành ổn định

Viết hàm xep_on_dinh(ds, key, ham_xep). ham_xep nhận một list và trả về một list mới đã xếp tăng dần, nhưng không ổn định. Hàm của bạn trả về list mới gồm các phần tử của ds xếp theo key(x), và phần tử có khóa bằng nhau giữ thứ tự cũ.

Cách làm: gắn cho mỗi phần tử một bộ (key(x), i, x) với i là vị trí ban đầu, gọi ham_xep đúng một lần, rồi lấy lại phần tử. Phần tử có thể là dict, vốn không so sánh được. Không dùng sorted() hay sort(), và đừng sửa ds.

Ví dụ: với key=lambda khach: khach["phut"], hai khách cùng 12 phút giữ thứ tự cũ.

Trả về: list các phần tử đã xếp, một list.

python
def xep_on_dinh(ds, key, ham_xep):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Bảy thuật toán hay gặp khác nhau ở độ phức tạp, bộ nhớ thêm, tính ổn định và tính tại chỗ.

  • O(n²) và O(n log n) gần nhau với list nhỏ nhưng cách nhau hàng chục nghìn lần với một triệu phần tử.

  • sort() và sorted() dùng Timsort: ổn định, O(n log n), và chỉ n - 1 phép so sánh với list đã xếp sẵn.

  • Sắp xếp ổn định cho phép xếp nhiều khóa: khóa phụ trước, khóa chính sau.

  • Gắn bộ (khóa, vị trí ban đầu, phần tử) biến mọi cách xếp thành ổn định.

Câu hỏi thường gặp

Thuật toán sắp xếp nào nhanh nhất?

Không có thuật toán nhanh nhất cho mọi dữ liệu. Với cách so sánh hai phần tử, O(n log n) là giới hạn dưới của trường hợp xấu nhất, nên merge sort và Timsort đã chạm tới đó. Số nguyên trong khoảng hẹp thì counting sort hay radix sort cần ít bước hơn. Trong Python, sort() viết bằng C gần như luôn nhanh hơn mọi bản tự viết bằng Python.

Hàm sort() của Python có ổn định không?

Có. Tài liệu Python bảo đảm list.sort() và sorted() ổn định, kể cả khi dùng reverse=True: các phần tử bằng nhau vẫn giữ thứ tự cũ.

Có nên tự viết thuật toán sắp xếp trong dự án thật?

Hầu như không. Hãy dùng sort() hay sorted() với key=. Chỉ tự viết khi đề bài yêu cầu, khi học, hay khi dữ liệu có dạng đặc biệt mà counting sort xử lý tốt hơn.

Chủ đề

thuật toán sắp xếp

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập