Một lượt đẩy số lớn về bên phải
Với `[5, 1, 4, 2]`, lượt đầu xét các cặp kề nhau từ trái sang phải. Đổi 5 với 1 được `[1, 5, 4, 2]`; đổi 5 với 4 được `[1, 4, 5, 2]`; đổi 5 với 2 được `[1, 4, 2, 5]`. Số lớn nhất 5 đã ở cuối. Lượt thứ hai chỉ xét ba vị trí đầu: cặp 1–4 giữ nguyên, cặp 4–2 đổi thành `[1, 2, 4, 5]`. Phần đuôi đã đúng thứ tự nên mỗi lượt sau có thể xét ít hơn một cặp.
Giới hạn vòng trong ngắn dần
```python
def sap_noi_bot_tang(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
print(sap_noi_bot_tang([5, 1, 4, 2]))
```
Kết quả là `[1, 2, 4, 5]`. Vòng trong so sánh đúng hai phần tử cạnh nhau; `n - 1 - i` tránh đụng phần đuôi đã đứng đúng chỗ. Dãy rỗng hoặc một phần tử giữ nguyên. Mã này vẫn chạy đủ các lượt của vòng ngoài dù dãy đã sắp; có thể thêm kiểm tra không lần đổi nào trong một lượt để dừng sớm, nhưng đó là biến thể khác.
Bài luyện
Sau lượt nổi bọt đầu tiên trên `[5,1,4,2]`, dãy là gì?
Số 5 đã chuyển qua ba cặp để về cuối.
Đây là kết quả sau lượt thứ hai.
Số 5 chưa được đẩy về cuối.
Không phải kết quả của các cặp xét từ trái sang phải.
Lời giải
Lượt đầu đổi 5–1, 5–4 và 5–2; dãy lần lượt thành [1,5,4,2], [1,4,5,2], [1,4,2,5].
Bài luyện
Vì sao vòng trong dùng `range(n - 1 - i)`?
Phần tử lớn đã dần về cuối.
Không có quy tắc số chẵn.
Mã không xóa phần tử.
a[n] vượt chỉ số cuối.
Lời giải
Sau mỗi lượt từ trái sang phải, một số lớn nhất của phần chưa sắp về cuối; giới hạn vòng trong thu ngắn đúng phần cần xét.
Bài luyện
Hàm nổi bọt mẫu làm gì với dãy đã sắp tăng?
Mã chưa có cờ dừng sớm.
Mã không có cờ ấy.
Điều kiện > không đổi cặp đúng thứ tự.
Dãy đã sắp là đầu vào hợp lệ.
Lời giải
Vòng ngoài vẫn chạy theo range(n-1), nhưng mọi phép kiểm a[j]>a[j+1] đều sai nên không đổi chỗ.
Đang học