Khái niệm
Sắp xếp chèn (insertion sort) xây dựng dãy đã sắp xếp từng phần tử một — giống như cách ta sắp xếp bài trong tay khi chơi bài: cầm từng lá bài lên và chèn vào vị trí đúng trong những lá bài đã có.
- Độ phức tạp thời gian:
- Tốt nhất: O(n) — dãy đã sắp xếp
- Xấu nhất: O(n²) — dãy sắp xếp ngược
- Độ phức tạp không gian: O(1)
- Ổn định: Có
Insertion sort thực sự hiệu quả với dãy ngắn (n < 50) hoặc dãy gần như đã sắp xếp. Trong thực tế, nhiều thuật toán O(n log n) chuyển sang dùng insertion sort khi kích thước mảng con nhỏ hơn ngưỡng nhất định.
Minh hoạ từng bước
Ví dụ sắp xếp [5, 2, 4, 6, 1, 3]:
i=1: key=2, dịch 5 sang phải → [2, 5, 4, 6, 1, 3]
i=2: key=4, dịch 5 sang phải → [2, 4, 5, 6, 1, 3]
i=3: key=6, không dịch → [2, 4, 5, 6, 1, 3]
i=4: key=1, dịch 6,5,4,2 phải → [1, 2, 4, 5, 6, 3]
i=5: key=3, dịch 6,5,4 phải → [1, 2, 3, 4, 5, 6]
Cài đặt cơ bản
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # Phần tử cần chèn
j = i - 1
# Dịch các phần tử lớn hơn key sang phải
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # Chèn key vào vị trí đúng
return arr
data = [5, 2, 4, 6, 1, 3]
print(insertion_sort(data)) # [1, 2, 3, 4, 5, 6]
Bài tập luyện tập
Dễ — Sắp xếp chuỗi theo độ dài
Sắp xếp danh sách chuỗi theo độ dài tăng dần.
def sap_xep_theo_do_dai(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and len(arr[j]) > len(key):
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
words = ["banana", "cat", "dog", "apple", "hi"]
print(sap_xep_theo_do_dai(words))
# ['hi', 'cat', 'dog', 'apple', 'banana']
Trung bình — Chèn phần tử vào dãy đã sắp xếp
Cho một dãy đã sắp xếp và một phần tử mới, chèn phần tử đó vào đúng vị trí mà không cần sắp xếp lại toàn bộ.
def chen_vao_day_sap_xep(arr, val):
"""Chèn val vào dãy đã sắp xếp, trả về dãy mới."""
arr = arr[:]
arr.append(val)
j = len(arr) - 2
while j >= 0 and arr[j] > val:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = val
return arr
sorted_arr = [1, 3, 5, 7, 9]
print(chen_vao_day_sap_xep(sorted_arr, 4)) # [1, 3, 4, 5, 7, 9]
print(chen_vao_day_sap_xep(sorted_arr, 0)) # [0, 1, 3, 5, 7, 9]
print(chen_vao_day_sap_xep(sorted_arr, 10)) # [1, 3, 5, 7, 9, 10]
Khó — Đếm số lần đảo ngược (inversion count)
Trong sắp xếp chèn, mỗi lần “dịch phần tử sang phải” tương ứng với một cặp nghịch thế (inversion). Đếm tổng số cặp nghịch thế — tức là số cặp (i, j) với i < j nhưng arr[i] > arr[j].
def dem_nghich_the(arr):
"""Đếm số cặp nghịch thế bằng insertion sort."""
arr = arr[:]
dem = 0
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
dem += 1 # Mỗi lần dịch = 1 nghịch thế
arr[j + 1] = key
return dem
print(dem_nghich_the([1, 2, 3, 4])) # 0 (không có nghịch thế)
print(dem_nghich_the([4, 3, 2, 1])) # 6 (6 cặp: (4,3),(4,2),(4,1),(3,2),(3,1),(2,1))
print(dem_nghich_the([2, 4, 1, 3, 5])) # 3
Kết luận
Insertion sort là thuật toán O(n²) thực dụng nhất trong nhóm. Với dữ liệu gần sắp xếp, nó chạy gần O(n) và thường nhanh hơn bubble sort hay selection sort. Tiếp theo, hãy học Sắp xếp trộn — một bước nhảy vọt từ O(n²) lên O(n log n).
Bình luận