Đổi yêu cầu thì đổi điều kiện
Sắp xếp **không giảm** giữ phần bên trái nhỏ trước, lớn sau: khi chèn `value`, dịch những phần tử `> value` sang phải. Nếu đầu ra cần **không tăng**, phần bên trái phải lớn trước, nhỏ sau; lúc này dịch những phần tử `< value` sang phải. Phần tử **bằng** `value` không cần dịch ở cả hai phiên bản. Chỉ nói “đổi chiều” trong mô tả mà vẫn dùng dấu `>` trong mã sẽ cho kết quả sai.
Phiên bản không tăng
```python
def sap_chen_giam(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
return a
print(sap_chen_giam([3, 1, 4, 3]))
```
Kết quả là `[4, 3, 3, 1]`. Với lượt chèn 4, các giá trị nhỏ hơn ở bên trái dịch sang phải; hai số 3 bằng nhau đều được giữ trong kết quả. Có thể tách phần dịch và đặt `value` thành một hàm nhỏ nếu chương trình cần dùng lại; ý nghĩa của điều kiện so sánh vẫn phải đúng với thứ tự yêu cầu.
Bài luyện
Muốn dùng sắp xếp chèn để xếp dãy không tăng, điều kiện nào dùng để dịch phần tử bên trái?
Dấu > dùng cho thứ tự không giảm.
Giá trị nhỏ hơn phải lùi về sau.
Giá trị bằng nhau không cần dịch.
Không phải phép so sánh giá trị.
Lời giải
Để phần lớn đứng trước, mỗi giá trị nhỏ hơn value ở bên trái được dịch sang phải.
Bài luyện
`sap_chen_giam([3, 1, 4, 3])` trả dãy nào?
Đây là thứ tự tăng.
1 phải ở sau cả hai số 3.
4 lớn nhất đứng trước; hai số 3 theo sau; 1 cuối.
3 đứng trước 4 là sai thứ tự giảm.
Lời giải
Sau mỗi lượt chèn, đoạn đầu không tăng; hết dãy được [4, 3, 3, 1].
Bài luyện
Khi chèn một giá trị bằng phần tử bên trái, mã dùng dấu `<` trong bài làm gì?
Điều kiện < sai khi hai giá trị bằng nhau.
Phần tử bằng không cần dịch để giữ thứ tự không tăng.
Mã không xoá phần tử.
Dãy có số trùng vẫn sắp được.
Lời giải
Nếu a[j] == value thì a[j] < value là False; vòng while dừng và đặt value ngay sau giá trị bằng.
Đang học