Thuật toán Python

Sắp xếp chèn (insertion sort) trong Python

Sắp xếp như khi xếp bài trên tay: lấy giá trị tiếp theo và trượt nó sang trái tới đúng chỗ.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • Mở rộng dần phần đầu đã sắp xếp
  • Dời các giá trị lớn hơn sang phải
  • Vì sao nó nhanh với dữ liệu gần như đã sắp xếp
Chèn 4 vào [1, 5, 9]
1giữ nguyên
4đã chèn
5dời →
9dời →
3tiếp theo
Ban đầu: [9, 5, 1, 4, 3]. Kết quả: [1, 3, 4, 5, 9].

Chèn mỗi giá trị vào phần đã sắp xếp

Vấn đề

Dữ liệu thường đến gần như đã có thứ tự, hoặc đến từng phần tử một: một list điểm đã sắp xếp nhận thêm một điểm mới. Sắp xếp lại toàn bộ là lãng phí. Sắp xếp chèn (insertion sort) xử lý trường hợp này rất tốt, và đó cũng là cách nhiều người xếp bài trên tay.

Hình dung đời thường

Insertion sort là cách bạn xếp bài trên tay. Bạn rút từng lá một và trượt nó sang trái qua mọi lá lớn hơn cho tới khi nó nằm đúng chỗ. Những lá bên trái nó lúc nào cũng đã đúng thứ tự.

Từ việc xếp bài đến code
current = result[index]🃏 Rút lá bài tiếp theo
result[position] > current👈 Lá bên trái có lớn hơn không?
result[position + 1] = result[position]➡️ Đẩy lá lớn hơn sang phải một chỗ
result[position + 1] = current📥 Thả lá bài vào chỗ trống
Phần bên trái luôn có thứ tự; mỗi phần tử mới được chèn vào đó.
Định nghĩa ngắn gọn

Insertion sort dựng dần phần đã sắp xếp, mỗi lần một phần tử, bằng cách đẩy các phần tử lớn hơn sang phải rồi chèn phần tử hiện tại vào chỗ trống; trường hợp xấu nhất là O(n²) nhưng gần O(n) với dữ liệu gần như đã có thứ tự.

Những điểm quan trọng

  1. for index in range(1, len(result)): bắt đầu từ phần tử thứ hai; một phần tử đứng riêng thì đã có thứ tự.
  2. current giữ giá trị đang được chèn trong lúc các giá trị lớn hơn dịch chuyển.
  3. while position >= 0 and result[position] > current: đẩy từng giá trị lớn hơn sang phải một chỗ.
  4. result[position + 1] = current thả giá trị vào chỗ trống vừa được mở ra.

Khi nào nên sử dụng?

  • List nhỏ hoặc gần như đã có thứ tự.
  • Giữ một list luôn có thứ tự khi phần tử mới liên tục đến.
  • Bước cuối bên trong các thuật toán sắp xếp nhanh, vốn chuyển sang insertion sort cho các đoạn nhỏ.

Khi nào chưa cần

  • List lớn có thứ tự ngẫu nhiên: việc dịch chuyển trở nên chậm, hãy dùng sorted().
  • Thường xuyên chèn vào một list lớn đã sắp xếp: bisect.insort tìm vị trí bằng tìm kiếm nhị phân.

Mô phỏng Sắp xếp chèn (insertion sort) trong Python

O(n²)

Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.

Code ví dụ

Chạy code →
main.py
def insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
Lấy nút Run cho ví dụ này

Kết quả khi chạy

[1, 3, 4, 5, 9]

Giải thích code

Biến current giữ giá trị đang cần chèn. Vòng lặp while dịch các giá trị lớn hơn current sang phải một vị trí để tạo chỗ trống, sau đó current được đặt vào đúng vị trí đó. Trong trường hợp xấu nhất, độ phức tạp là O(n²), nhưng với dữ liệu gần như đã sắp xếp, thuật toán gần đạt O(n).

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.

  1. Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Chạy trong trình biên dịch Python →

Lỗi hay gặp

Ghi current trở lại ngay trong vòng lặp

Giá trị chỉ được đặt một lần, sau khi mọi giá trị lớn hơn đã dịch chuyển xong.

Sai
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
Cách sửa
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

Bạn học xong bài này chưa?

Đánh dấu đã học để theo dõi tiến độ của bạn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách