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ỗ.
- 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 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ự.
current = result[index]🃏 Rút lá bài tiếp theoresult[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ốngInsertion 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
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ự.currentgiữ giá trị đang được chèn trong lúc các giá trị lớn hơn dịch chuyển.while position >= 0 and result[position] > current:đẩy từng giá trị lớn hơn sang phải một chỗ.result[position + 1] = currentthả 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.insorttì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ụ
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]))
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.
- 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.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đ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.
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.
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
result[position] = current
position -= 1
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