0

Thuật toán & CTDL #03: Insertion Sort - thuật toán xếp bài mà Timsort vẫn dùng mỗi ngày

Mỗi lần xếp bài trên tay, bạn đang chạy Insertion Sort mà không biết: nhấc một lá lên, so với các lá bên trái, dịch những lá lớn hơn sang, rồi thả lá đó vào đúng chỗ. Nghe đơn giản, và đúng là O(n²) trong trường hợp tệ nhất. Vậy mà Timsort, thuật toán đứng sau sorted() của Python, vẫn dùng nó cho các đoạn nhỏ. Bài này giải thích vì sao.

Ý tưởng

Giữ phần bên trái mảng luôn được sắp xếp. Ban đầu phần đó chỉ có một phần tử (một phần tử thì luôn được sắp). Với mỗi phần tử tiếp theo:

  1. Nhấc nó ra, gọi là key.
  2. Đi ngược sang trái: phần tử nào lớn hơn key thì dịch sang phải một ô. Không đổi chỗ, chỉ dịch.
  3. Gặp phần tử nhỏ hơn hoặc bằng key, hoặc chạm mép trái, thì thả key xuống ô trống.

Chạy tay một ví dụ

Mảng trong video: [5, 2, 8, 1, 7, 3, 6, 4].

Nhấc Số so sánh Số lần dịch Mảng sau bước
2 1 1 [2, 5, 8, 1, 7, 3, 6, 4]
8 1 0 [2, 5, 8, 1, 7, 3, 6, 4]
1 3 3 [1, 2, 5, 8, 7, 3, 6, 4]
7 2 1 [1, 2, 5, 7, 8, 3, 6, 4]
3 4 3 [1, 2, 3, 5, 7, 8, 6, 4]
6 3 2 [1, 2, 3, 5, 6, 7, 8, 4]
4 5 4 [1, 2, 3, 4, 5, 6, 7, 8]

Tổng: 19 lần so sánh, 14 lần dịch. Ít hơn hẳn 25 lần của Bubble Sort và 28 lần của Selection Sort trên cùng mảng.

Để ý bước nhấc số 8: chỉ cần một lần so sánh (8 > 5), thả xuống ngay. Đó là chìa khóa của thuật toán này.

Code Python

def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:   # > (không phải >=) để giữ stable
            a[j + 1] = a[j]            # dịch sang phải, không đổi chỗ
            j -= 1
        a[j + 1] = key                 # thả vào ô trống
    return a

print(insertion_sort([5, 2, 8, 1, 7, 3, 6, 4]))  # [1, 2, 3, 4, 5, 6, 7, 8]
print(insertion_sort([1, 2, 3, 5, 4]))           # [1, 2, 3, 4, 5]

Độ phức tạp

  • Tệ nhất (mảng sắp ngược): phần tử thứ i phải dịch qua cả i phần tử, tổng n(n-1)/2, tức O(n²).
  • Trung bình: O(n²).
  • Tốt nhất (mảng đã sắp): mỗi phần tử chỉ cần một lần so sánh, tổng n-1, tức O(n).
  • Bộ nhớ: O(1), in-place.
  • Stable: có.

Chính xác hơn, thời gian chạy là O(n + k), với k là số nghịch thế (cặp phần tử đứng sai thứ tự) trong mảng. Mỗi lần dịch sửa đúng một nghịch thế. Mảng gần sắp xếp nghĩa là k nhỏ, và Insertion Sort chạy gần như tuyến tính. Đây gọi là tính adaptive: dữ liệu càng gần đúng thì chạy càng nhanh.

Insertion Sort còn là thuật toán online: nó sắp được dữ liệu đến dần dần, không cần biết trước toàn bộ mảng. Mỗi phần tử mới chỉ cần chèn vào phần đã sắp.

Vì sao các thư viện xịn vẫn dùng nó?

  • Timsort (dùng trong sorted()/list.sort() của Python, và Arrays.sort cho mảng object trong Java) chia dữ liệu thành các đoạn (run). Đoạn nào ngắn hơn một ngưỡng nhỏ (cỡ 32 đến 64 phần tử) thì được kéo dài và sắp bằng binary insertion sort: tìm vị trí chèn bằng tìm kiếm nhị phân, rồi dịch.
  • Dual-Pivot Quicksort của Java cho kiểu nguyên thủy, và introsort trong nhiều bản cài đặt std::sort của C++, cũng chuyển sang insertion sort khi đoạn con đủ nhỏ.

Lý do: với n nhỏ, hằng số mới là thứ quyết định. Insertion Sort không đệ quy, không cấp phát bộ nhớ, truy cập bộ nhớ tuần tự nên rất thân thiện với cache. Trên vài chục phần tử, nó thường thắng các thuật toán O(n log n).

Khi nào dùng, khi nào không

Dùng khi:

  • Mảng nhỏ (vài chục phần tử).
  • Dữ liệu gần như đã sắp, ví dụ danh sách đã sắp rồi được thêm vài phần tử mới.
  • Dữ liệu đến theo luồng và cần luôn giữ thứ tự.

Không dùng khi mảng lớn và thứ tự ngẫu nhiên. 1 triệu phần tử sắp ngược cần khoảng 500 tỷ lần dịch, không khác gì Bubble Sort.

Lỗi hay gặp

  1. Đổi thứ tự điều kiện: viết a[j] > key and j >= 0. Trong Python, khi j = -1 thì a[-1] vẫn hợp lệ (phần tử cuối), nên code không báo lỗi mà cho kết quả sai. Luôn kiểm tra j >= 0 trước.
  2. Dùng swap thay vì dịch: vẫn đúng, nhưng mỗi bước tốn 3 phép gán thay vì 1.
  3. Dùng >=: mất tính stable.
  4. Nghĩ binary insertion sort là O(n log n): tìm kiếm nhị phân chỉ giảm số so sánh xuống O(n log n), còn số lần dịch vẫn O(n²).

Câu hỏi phỏng vấn hay gặp

  • Insertion Sort tốt nhất khi nào? Mảng đã sắp hoặc gần sắp: O(n), chính xác là O(n + số nghịch thế).
  • So với Selection Sort? Insertion Sort adaptive và stable, Selection Sort thì không. Đổi lại Selection Sort ghi ít hơn.
  • Vì sao Timsort dùng Insertion Sort? Với đoạn nhỏ, hằng số thấp và thân thiện cache quan trọng hơn độ phức tạp tiệm cận.

Lời kết

Ba thuật toán đầu series đều O(n²), nhưng Insertion Sort là cái duy nhất vẫn sống khỏe trong code production, chỉ là nằm ẩn bên trong các thư viện. Muốn vượt hẳn rào O(n²) thì cần một chiến lược khác: chia để trị.

Đây là bài 03/19 của series "Thuật toán & Cấu trúc dữ liệu - Giải thuật". Bản video ngắn có hoạt hình minh họa từng lá bài được nhấc lên và thả xuống nằm trên page Trà Đá Tech: https://www.facebook.com/profile.php?id=61596642752252

Bạn có biết thư viện nào khác cũng ngầm dùng Insertion Sort không? Hãy chia sẻ trong phần bình luận.

Nếu thấy bài viết hữu ích, hãy upvote và follow để theo dõi các bài tiếp theo.

Bài tiếp theo: Merge Sort - chia để trị, nhanh gấp khoảng 25.000 lần Bubble Sort với 1 triệu số


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí