Bên trái đã sắp, bên phải còn chờ
Cho dãy `[6, 2, 5, 1]` cần sắp **không giảm**. Coi phần tử đầu `[6]` là phần đã sắp. Lấy 2, dịch 6 sang phải và đặt 2 trước 6: `[2, 6, 5, 1]`. Lấy 5, dịch 6 rồi đặt 5 sau 2: `[2, 5, 6, 1]`. Lấy 1, dịch lần lượt 6, 5, 2 sang phải rồi đặt 1 ở đầu: `[1, 2, 5, 6]`. Sau mỗi lượt, phần từ đầu đến vị trí vừa xét đã sắp đúng; đó là lí do lượt tiếp theo chỉ cần chèn thêm một phần tử.
Giữ giá trị đang chèn trước khi dịch
```python
def sap_chen_tang(a):
for i in range(1, len(a)):
gia_tri = a[i]
j = i - 1
while j >= 0 and a[j] > gia_tri:
a[j + 1] = a[j]
j -= 1
a[j + 1] = gia_tri
return a
print(sap_chen_tang([6, 2, 5, 1]))
```
Kết quả là `[1, 2, 5, 6]`. Biến `gia_tri` giữ số cần chèn; nếu không giữ trước, thao tác dịch có thể ghi đè nó. Vòng `while` chỉ dịch những số **lớn hơn** `gia_tri`. Với dãy đã sắp, vòng ngoài vẫn xét từng phần tử và vẫn so sánh điều kiện, nhưng vòng trong không dịch số nào. Hàm sửa chính danh sách nhận vào; dãy rỗng hoặc một phần tử giữ nguyên. Dấu `>` giúp các phần tử bằng nhau không bị dịch qua nhau.
Bài luyện
Sau lượt chèn số 5 trong dãy ban đầu `[6, 2, 5, 1]`, dãy là gì?
Phần đã xét gồm 2, 5, 6 đúng thứ tự.
Đây là sau khi chèn 2, chưa chèn 5.
Đây là kết quả cuối sau khi chèn 1.
Phần bên trái chưa tăng.
Lời giải
Sau lượt đầu là [2,6,5,1]. Lượt tiếp theo dịch 6 sang phải rồi đặt 5 sau 2, được [2,5,6,1].
Bài luyện
Trong hàm sắp chèn, vì sao cần lưu `gia_tri = a[i]` trước vòng dịch?
Giữ số cần chèn cho đến lúc đặt vào vị trí mới.
Python so sánh số được.
Không cần đổi sang chuỗi.
Thuật toán dùng cho nhiều phần tử.
Lời giải
Khi a[j] được chép sang a[j+1], ô cũ của giá trị cần chèn có thể bị thay. Biến gia_tri giữ giá trị ấy.
Bài luyện
Với dãy đã sắp tăng, hàm sắp chèn mẫu thực hiện điều gì?
Vòng for và phép kiểm while vẫn chạy.
Vòng for vẫn duyệt từ chỉ số 1.
Điều kiện > không đảo dãy.
Hàm không xóa phần tử.
Lời giải
Khi a[j] không lớn hơn gia_tri, điều kiện while sai ngay; không dịch, nhưng vòng for vẫn xét từng i.
Đang học