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

Coi phần tử đầu tiên là danh sách đã sắp xếp có độ dài một. Lấy phần tử thứ hai và chèn vào trước hoặc sau phần tử đầu. Lấy phần tử thứ ba và chèn vào đúng chỗ giữa hai phần tử đầu. Tiếp tục cho đến khi mọi phần tử đã được chèn.

Để chèn, hãy để phần tử mới sang một bên (gọi là key), rồi đi sang trái qua phần đã sắp xếp. Mọi phần tử lớn hơn key dịch sang phải một vị trí. Khi gặp phần tử không lớn hơn, hoặc đến đầu danh sách, đặt key vào ô trống.

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

Sắp xếp [12, 11, 13, 5, 6]. Phần trước dấu gạch đã được sắp xếp (nhưng chưa phải vị trí cuối cùng).

Lưu ý bước 2: phần tử đã đúng chỗ chỉ tốn một phép so sánh. Đó là lý do sắp xếp chèn nhanh với đầu vào gần như đã sắp xếp.

Cài đặt bằng Python

def insertion_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:   # strict >, keeps it stable
            items[j + 1] = items[j]        # shift right
            j -= 1
        items[j + 1] = key                 # drop into the gap
    return items
print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]
print(insertion_sort([1, 2, 3, 4]))         # [1, 2, 3, 4], 3 comparisons

Dịch chuyển thay vì đổi chỗ chỉ ghi mỗi phần tử được di chuyển một lần, bằng khoảng một nửa công việc của phiên bản đổi chỗ. Bạn cũng có thể tìm điểm chèn bằng tìm kiếm nhị phân như dưới đây. Cách này giảm số phép so sánh xuống O(n log n) tổng cộng, nhưng việc dịch chuyển vẫn là O(n²), nên thời gian tổng thể vẫn là O(n²).

from bisect import insort_right
def binary_insertion_sort(items):
    result = []
    for x in items:
        insort_right(result, x)   # stable: equal items go after
    return result
print(binary_insertion_sort([3, 1, 2, 1]))   # [1, 1, 2, 3]

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

Chính xác hơn, thời gian chạy là O(n + I), trong đó I là số nghịch thế (các cặp sai thứ tự). Nếu mọi phần tử cách vị trí cuối cùng của nó tối đa k vị trí, I nhiều nhất là n · k, nên sắp xếp chèn là O(n · k): rất nhanh khi k nhỏ.

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

Sắp xếp chèn ổn định vì một phần tử chỉ di chuyển sang trái qua các phần tử thực sự lớn hơn nó. Nó cũng là thuật toán trực tuyến (online): có thể sắp xếp dữ liệu khi nó đến, luôn giữ một tiền tố đã sắp xếp. Với danh sách ngắn, chi phí phụ thấp của nó thắng các thuật toán O(n log n), nên Timsort (dùng trong Python và trong Java cho đối tượng) sắp xếp các đoạn ngắn bằng sắp xếp chèn nhị phân, và nhiều bản cài đặt sắp xếp nhanh chuyển sang sắp xếp chèn khi kích thước nhỏ.

Biến thể và lỗi thường gặp

• Sắp xếp chèn nhị phân: tìm vị trí bằng tìm kiếm nhị phân rồi mới dịch chuyển. Ít phép so sánh hơn, có lợi khi việc so sánh tốn kém.
• Shell sort: chạy sắp xếp chèn trên các phần tử cách nhau một khoảng (gap), rồi thu nhỏ khoảng đó xuống 1. Nó di chuyển nhanh các phần tử ở xa và nhanh hơn nhiều so với sắp xếp chèn thường trên mảng lớn.
• Sắp xếp chèn trên danh sách liên kết: không cần dịch chuyển, nhưng tìm vị trí vẫn là quét tuyến tính.

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

Dùng nó cho mảng nhỏ (vài chục phần tử), cho dữ liệu gần như đã sắp xếp, như list đã sắp xếp rồi thêm vài phần tử ở cuối, và khi bạn cần một thuật toán sắp xếp tại chỗ ổn định đơn giản. Với dữ liệu ngẫu nhiên lớn, hãy dùng thuật toán O(n log n); trong Python đó là sorted() hoặc list.sort(), vốn đã áp dụng sắp xếp chèn cho các đoạn nhỏ bên trong.

Câu hỏi phỏng vấn thường yêu cầu theo dõi các bước, trường hợp tốt nhất và xấu nhất, vì sao nó ổn định, hoặc vì sao nó thắng các thuật toán O(n log n) trên đầu vào nhỏ và gần như đã sắp xếp.