Đổi chiều so sánh ở đúng nơi
Ở sắp chèn tăng, những số **lớn hơn** giá trị đang chèn được dịch sang phải. Muốn sắp giảm, dịch những số **nhỏ hơn** để số lớn ở trước. Ở nổi bọt tăng, cặp `a[j] > a[j+1]` bị đổi để số lớn sang phải; muốn giảm, đổi khi `a[j] < a[j+1]` để số lớn sang trái. Giữ nguyên cách tính chỉ số và giới hạn vòng lặp.
Hai hàm sắp giảm
```python
def sap_chen_giam(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
def sap_noi_bot_giam(a):
n = len(a)
for i in range(n - 1):
for j in range(n - 1 - i):
if a[j] < a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
return a
goc = [4, 1, 6, 3, 6]
print(sap_chen_giam(goc.copy()))
print(sap_noi_bot_giam(goc.copy()))
```
Hai dòng đều in `[6, 6, 4, 3, 1]`. `copy()` tạo hai danh sách riêng vì mỗi hàm sửa tại chỗ; nếu dùng cùng một danh sách thì hàm thứ hai nhận dữ liệu đã được sắp. Hai số 6 vẫn được giữ đủ. Dãy rỗng và dãy một phần tử không cần đổi chỗ. Với bản sắp chọn giảm ở L21, ba cách sắp giảm trong phần vận dụng SGK đã được thực hiện.
Bài luyện
Trong sắp chèn giảm, khi nào dịch `a[j]` sang phải?
Số nhỏ hơn phải đứng sau giá trị đang chèn.
Đây là điều kiện của sắp tăng.
j<0 là ngoài phần đầu cần xét.
Chỉ dịch số đứng sai thứ tự.
Lời giải
Để số lớn đứng trước, mọi số nhỏ hơn gia_tri ở phần bên trái phải dịch sang phải nhường chỗ.
Bài luyện
Trong nổi bọt giảm, cặp `[2, 5]` kề nhau được xử lí thế nào?
Thứ tự giảm cần số lớn đứng trước.
Vì 2<5, đổi hai vị trí kề nhau.
Thuật toán không xóa.
Thuật toán không cộng cặp.
Lời giải
Điều kiện a[j]<a[j+1] đúng với cặp [2,5], nên đổi để 5 đứng trước 2.
Bài luyện
Vì sao ví dụ dùng `goc.copy()` cho mỗi hàm sắp?
Mỗi bản sao bắt đầu với [4,1,6,3,6].
copy vẫn giữ các số.
copy vẫn giữ cả hai số 6.
Hai hàm vẫn được gọi.
Lời giải
Nếu truyền goc trực tiếp, hàm đầu sẽ sửa goc và hàm sau nhận dãy đã sắp. copy tạo hai đầu vào độc lập để so sánh.
Đang học