Thuật toán sắp xếp chọn: cách hoạt động, mã và độ phức tạp

Ý tưởng bằng lời đơn giản

Quét toàn bộ danh sách và tìm phần tử nhỏ nhất. Đổi chỗ nó với phần tử ở chỉ số 0; lúc này chỉ số 0 đã cố định. Quét phần còn lại từ chỉ số 1, tìm phần tử nhỏ nhất và đổi chỗ vào chỉ số 1. Tiếp tục cho đến khi chỉ còn một phần tử, chắc chắn là phần tử lớn nhất.

Khác với sắp xếp nổi bọt và sắp xếp chèn, sắp xếp chọn không hưởng lợi từ đầu vào đã sắp xếp: nó vẫn phải quét mọi phần tử còn lại để chắc chắn đã tìm ra giá trị nhỏ nhất.

Ví dụ minh họa từng bước

Sắp xếp [64, 25, 12, 22, 11]. Phần trước dấu gạch đã được sắp xếp và cố định.

Bốn bước cho năm phần tử, với 4 + 3 + 2 + 1 = 10 phép so sánh và ba lần đổi chỗ thật sự.

Cài đặt bằng Python

def selection_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]
    return items
print(selection_sort([64, 25, 12, 22, 11]))   # [11, 12, 22, 25, 64]
print(selection_sort([2, 1]))                 # [1, 2]

Vòng lặp ngoài chạy n − 1 lần vì phần tử còn lại cuối cùng tự động đúng chỗ. Vòng lặp trong chỉ ghi lại một chỉ số; việc đổi chỗ chỉ xảy ra một lần ở mỗi bước ngoài.

Độ phức tạp thời gian và không gian

Số lần ghi ít là điểm mạnh thực sự duy nhất của sắp xếp chọn. Nếu việc ghi vào bộ nhớ tốn kém hơn nhiều so với đọc, như với một số bộ nhớ flash hoặc khi di chuyển các bản ghi lớn, ít lần ghi hơn có thể quan trọng. Cycle sort đẩy điều này xa hơn và ghi mỗi phần tử tối đa một lần.

Tính ổn định: vì sao sắp xếp chọn không ổn định

Một thuật toán sắp xếp ổn định giữ nguyên thứ tự tương đối ban đầu của các phần tử bằng nhau. Phép đổi chỗ xa của sắp xếp chọn có thể làm một phần tử nhảy qua phần tử khác bằng nó.

def selection_sort_by_key(items, key):
    n = len(items)
    for i in range(n - 1):
        m = min(range(i, n), key=lambda j: key(items[j]))
        items[i], items[m] = items[m], items[i]
    return items
cards = [("4", "hearts"), ("4", "spades"), ("2", "clubs")]
print(selection_sort_by_key(cards, key=lambda c: c[0]))
# [('2', 'clubs'), ('4', 'spades'), ('4', 'hearts')]  order of the 4s changed

Số 2 đã được đổi chỗ với quân 4 cơ, khiến quân 4 cơ nằm sau quân 4 bích. Có một phiên bản ổn định: thay vì đổi chỗ, lấy giá trị nhỏ nhất ra và chèn vào vị trí i, dịch các phần tử khác sang phải. Cách này giữ được thứ tự nhưng tốn O(n) lần ghi mỗi bước.

So sánh sắp xếp chọn với các thuật toán khác

Sắp xếp vun đống (heapsort) chính là sắp xếp chọn với cấu trúc dữ liệu tốt hơn: nó cũng liên tục chọn phần tử lớn nhất còn lại, nhưng tìm nó trong O(log n) bằng đống nhị phân thay vì quét O(n), nhờ đó tổng thể là O(n log n).

Khi nào nên dùng sắp xếp chọn

Trong mã Python thực tế, hãy dùng sorted() hoặc list.sort() có sẵn. Sắp xếp chọn đáng biết như ví dụ giảng dạy, cho các mảng cố định rất nhỏ trong môi trường hạn chế, và khi số lần ghi phải tối thiểu. Đây là câu hỏi thi và phỏng vấn thường gặp, thường dưới dạng: theo dõi các bước, đếm số phép so sánh và đổi chỗ, và giải thích vì sao nó không ổn định.