Sau mỗi lượt, phần đầu đã đúng thứ tự
Sắp xếp chèn lấy phần tử tiếp theo rồi đưa nó vào phần đầu đã sắp. Mệnh đề cần giữ là: **trước lượt có chỉ số `i`, đoạn `a[0:i]` đã sắp không giảm và vẫn chứa đúng các phần tử ban đầu của đoạn ấy**. Ban đầu, đoạn chỉ có một phần tử nên mệnh đề đúng. Sau khi chèn `a[i]` vào vị trí thích hợp, đoạn dài thêm một phần tử vẫn không giảm và không mất phần tử nào. Khi đã xử lí đến cuối dãy, cả dãy được sắp.
“Không giảm” nghĩa là phần tử sau **lớn hơn hoặc bằng** phần tử trước. Điều này cho phép hai giá trị bằng nhau, như `[2, 2, 5]`. Chỉ nói các phần tử tăng nghiêm ngặt sẽ bỏ sót trường hợp ấy.
Chèn phần tử 2 vào phần đầu
Với `a = [1, 4, 2]`, trước lượt `i = 2`, phần đầu `[1, 4]` đã sắp. Giữ `value = 2`, dịch `4` sang phải, dừng ở `1` vì `1 <= 2`, rồi đặt `2` vào giữa. Kết quả là `[1, 2, 4]`. Mã dùng điều kiện `a[j] > value` nên không dịch phần tử bằng `value`:
```python
def sap_chen(a):
for i in range(1, len(a)):
value = a[i]
j = i - 1
while j >= 0 and a[j] > value:
a[j + 1] = a[j]
j -= 1
a[j + 1] = value
```
Phần đầu đã sắp là điều kiện dùng cho **mọi lượt**; một vài dãy thử chỉ minh họa, không tự chứng minh mệnh đề.
Bài luyện
Trước lượt `i` của sắp xếp chèn, đoạn nào đã được sắp theo bất biến?
Đoạn từ chỉ số 0 đến i−1 đã được xử lí.
Đoạn sau chưa được xử lí.
Cả dãy chỉ chắc chắn sau lượt cuối.
Một phần tử chưa mô tả phần đầu đã sắp.
Lời giải
Trước lượt i, các phần tử a[0] đến a[i−1] tạo phần đầu đã sắp.
Bài luyện
Với `a = [1, 4, 2]`, sau khi chèn phần tử cuối bằng mã trong bài, dãy là gì?
4 phải dịch sang phải.
1 không lớn hơn 2 nên không dịch.
2 được đặt sau 1, trước 4.
Đây là thứ tự giảm.
Lời giải
Giữ 2, dịch 4 sang vị trí cuối rồi đặt 2 sau 1: [1, 2, 4].
Bài luyện
Vì sao phát biểu “dãy sau sắp tăng nghiêm ngặt” không phù hợp cho đầu vào `[2, 2, 5]`?
Độ dài không gây vấn đề.
Cần phát biểu “không giảm”, cho phép bằng nhau.
Chẵn lẻ không liên quan.
Thuật toán nhận dãy bất kì.
Lời giải
Dãy có phần tử trùng vẫn sắp được. Thứ tự đúng là không giảm: a[k] ≤ a[k+1].
Đang học