Skip to main content

📘 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

· 3 min read

📝 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ướcDanh sáchMô 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)

📺 Video hướng dẫn YouTube​

🎬 Video chia sẻ nhanh TikTok​

📌 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ỗ).