Ba cách làm, cùng một đích
Cả ba thuật toán đều có thể đưa dãy số về thứ tự tăng hoặc giảm. **Chèn** lấy một số rồi đặt nó vào phần bên trái đã sắp. **Chọn** tìm số nhỏ nhất trong phần chưa sắp để đưa về đầu phần đó. **Nổi bọt** liên tiếp so sánh hai số kề nhau, đẩy số lớn về cuối sau mỗi lượt. Chúng dùng các phép so sánh/di chuyển khác nhau; trong Bài 21, điều quan trọng là truy vết đúng từng bước và điều kiện dừng, chưa cần xếp hạng thuật toán nào “tốt nhất” cho mọi dữ liệu.
Sắp giảm bằng cách chọn số lớn nhất
Muốn sắp giảm, ở mỗi lượt sắp xếp chọn cần đưa số **lớn nhất** của đoạn còn lại về đầu đoạn:
```python
def sap_chon_giam(a):
n = len(a)
for i in range(n - 1):
i_lon_nhat = i
for j in range(i + 1, n):
if a[j] > a[i_lon_nhat]:
i_lon_nhat = j
if i_lon_nhat != i:
a[i], a[i_lon_nhat] = a[i_lon_nhat], a[i]
return a
print(sap_chon_giam([4, 1, 6, 3]))
```
Kết quả là `[6, 4, 3, 1]`. Lượt đầu chọn 6, đổi với 4; lượt sau chọn 4 trong phần còn lại. Tương tự, ở sắp xếp chèn giảm, dịch các số **nhỏ hơn** giá trị cần chèn; ở nổi bọt giảm, đổi cặp kề nhau khi số bên trái **nhỏ hơn** bên phải. Chỉ thay phép so sánh, vẫn giữ giới hạn chỉ số và điều kiện dừng.
Sắp danh sách có tên thì chuyển cả bản ghi
Nếu mỗi phần tử là một cặp `(tên, điểm)`, sắp theo điểm phải di chuyển **cả cặp**. Chỉ đổi chỗ các điểm mà giữ danh sách tên nguyên vị trí sẽ ghép sai người và điểm. Khi điểm bằng nhau và cần giữ thứ tự tên ban đầu, phải chọn cách cài đặt phù hợp và kiểm trường hợp trùng; không suy điều đó chỉ từ kết quả các điểm đã có thứ tự.
Bài luyện
Sắp xếp chọn giảm: tại mỗi lượt cần chọn gì ở phần chưa sắp?
Đưa số nhỏ nhất về đầu tạo thứ tự tăng.
Số lớn nhất đúng ở vị trí đầu của phần còn lại.
Đó là thao tác của nổi bọt, không phải chọn.
Phải so sánh để biết số lớn nhất.
Lời giải
Muốn thứ tự giảm, phần đầu cần các số lớn hơn. Mỗi lượt chọn số lớn nhất của đoạn còn lại và đưa về đầu đoạn.
Bài luyện
Trong sắp xếp nổi bọt giảm, khi nào đổi hai phần tử kề nhau?
Điều kiện này đẩy số lớn sang phải để sắp tăng.
Số lớn hơn cần chuyển sang bên trái.
Bằng nhau đã đúng thứ tự theo giá trị.
Chỉ đổi khi cặp sai thứ tự.
Lời giải
Thứ tự giảm đòi số bên trái ≥ số bên phải. Nếu số trái nhỏ hơn, đổi để số lớn hơn sang trái.
Bài luyện
Khi sắp điểm của các bản ghi `(tên, điểm)`, điều nào giữ kết quả tra tên đúng?
Tên phải đi cùng điểm của người đó.
Cách này làm lệch tên và điểm.
Xóa tên thì không tra được tên.
Bỏ các bản ghi khác.
Lời giải
Một bản ghi gồm tên và điểm. Sắp theo điểm phải di chuyển toàn bản ghi để mối liên hệ không bị sai.
Đang học