📘 Ngày 9: Cấu trúc Dữ liệu và Giải thuật hằng ngày
Thuật toán Insertion Sort – Sắp xếp chèn
📝 Yêu cầu
Viết chương trình sắp xếp một danh sách số nguyên theo thứ tự tăng dần bằng thuật toán Insertion Sort.
🔍 Giải thích thuật toán
Insertion Sort là một thuật toán đơn giản hoạt động giống như cách bạn sắp xếp bài trên tay.
- Ta chia danh sách thành 2 phần:
- Phần đã sắp xếp (bắt đầu với 1 phần tử đầu tiên).
- Phần chưa sắp xếp.
- Từng bước, lấy phần tử đầu tiên của phần chưa sắp xếp, chèn vào đúng vị trí trong phần đã sắp xếp.
🧩 Ví dụ minh họa
Cho danh sách: [5, 2, 4, 6, 1, 3]
| Bước | Danh sách | Mô tả |
|---|---|---|
| 1 | [5, 2, 4, 6, 1, 3] | Bắt đầu với phần tử đầu tiên |
| 2 | [2, 5, 4, 6, 1, 3] | 2 < 5 ⇒ chèn 2 vào trước 5 |
| 3 | [2, 4, 5, 6, 1, 3] | 4 chèn giữa 2 và 5 |
| 4 | [2, 4, 5, 6, 1, 3] | 6 đúng vị trí, không đổi |
| 5 | [1, 2, 4, 5, 6, 3] | 1 chèn vào đầu danh sách |
| 6 | [1, 2, 3, 4, 5, 6] | 3 chèn vào giữa 2 và 4 |
🧑💻 Mã Python: Insertion Sort
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ời 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 đúng vị trí
# Nhập danh sách từ người dùng
arr = list(map(int, input("Nhập các số cách nhau bởi dấu cách: ").split()))
insertion_sort(arr)
print("Danh sách sau khi sắp xếp:", arr)
📌 Lưu ý
- Độ phức tạp thời gian:
- Trường hợp xấu nhất (ngược thứ tự): O(n^2)
- Trường hợp tốt nhất (đã sắp xếp): O(n)
- Không cần thêm bộ nhớ phụ (sắp xếp tại chỗ).