Đi ngược đến khi đúng vị trí
Cách trước giữ phần tử cần chèn trong `value` rồi dịch các phần tử lớn hơn. Cách khác bắt đầu từ vị trí `i` và liên tục **đổi chỗ với phần tử ngay bên trái** khi cặp này sai thứ tự: `a[j] < a[j−1]`. Sau mỗi lần đổi, giá trị mới đi một bước về bên trái. Khi đã đến đầu dãy hoặc phần tử bên trái không lớn hơn, dừng. Kết thúc lượt `i`, phần từ đầu đến `i` không giảm. Cả hai cách đều thực hiện ý tưởng sắp xếp chèn, dù các phép gán khác nhau.
Cài đặt và quan sát
```python
def sap_chen_doi_cho(a):
for i in range(1, len(a)):
j = i
while j > 0 and a[j] < a[j - 1]:
a[j], a[j - 1] = a[j - 1], a[j]
j -= 1
return a
print(sap_chen_doi_cho([4, 2, 2, 1]))
```
Kết quả là `[1, 2, 2, 4]`. Hai số 2 bằng nhau không đổi chỗ vì điều kiện `<` sai. Với `[3, 1, 2]`, lượt chèn 1 cho `[1, 3, 2]`; lượt chèn 2 đổi với 3, được `[1, 2, 3]`. Dãy rỗng hoặc một phần tử cũng cho kết quả đúng vì không cần lượt chèn nào.
Bài luyện
Trong phiên bản đổi chỗ liên tiếp, khi nào đổi `a[j]` với `a[j−1]`?
Cặp kề nhau sai thứ tự không giảm.
Hai giá trị bằng nhau đã đúng thứ tự.
j=0 không có phần tử bên trái.
Chỉ đổi cặp sai thứ tự.
Lời giải
Nếu giá trị bên phải nhỏ hơn bên trái, đổi chỗ sẽ đưa giá trị nhỏ hơn về trước.
Bài luyện
Sau lượt chèn giá trị 2 trong dãy đang là `[1, 3, 2]`, dãy thành gì?
3 và 2 vẫn sai thứ tự.
1 đã nhỏ hơn 2 nên không đổi.
Đổi cặp kề nhau 3 và 2 một lần.
Mã sắp tăng, không sắp giảm.
Lời giải
2 < 3 nên đổi hai vị trí cuối; 2 không nhỏ hơn 1 nên dừng tại [1, 2, 3].
Bài luyện
Với `[4, 2, 2, 1]`, kết quả của `sap_chen_doi_cho` là gì?
Sắp không giảm và giữ cả hai số 2.
Mã không xoá phần tử trùng.
Có nhiều cặp sai thứ tự cần đổi.
Đây chưa là dãy không giảm.
Lời giải
Các phần tử được chèn lần lượt về đúng vị trí, cho [1, 2, 2, 4]; không mất phần tử trùng.
Đang học