Vòng trong ngắn dần
Trong sắp xếp chọn tăng dần, lượt ngoài `i = 0` so sánh với `n−1` phần tử còn lại; lượt `i = 1` so sánh `n−2` phần tử; lượt cuối so sánh 1 phần tử. Tổng số lần kiểm `a[j] < a[vi_tri_nho_nhat]` là:
`(n−1) + (n−2) + … + 1 = n(n−1)/2`.
Với `n = 5`, số so sánh là `4 + 3 + 2 + 1 = 10`. Khi `n` lớn, hạng `n²/2` chi phối, nên bậc thời gian là `O(n²)`. Ở phiên bản sắp xếp chọn này, số lần **so sánh** vẫn là 10 dù dãy năm phần tử ban đầu đã sắp hay đảo ngược; số lần cập nhật vị trí nhỏ nhất có thể khác.
Kiểm bằng mã và mẫu nhỏ
```python
def sap_chon_va_dem(a):
so_sanh = 0
for i in range(len(a) - 1):
vi_tri_nho_nhat = i
for j in range(i + 1, len(a)):
so_sanh += 1
if a[j] < a[vi_tri_nho_nhat]:
vi_tri_nho_nhat = j
a[i], a[vi_tri_nho_nhat] = a[vi_tri_nho_nhat], a[i]
return so_sanh
day = [5, 1, 4, 2, 3]
print(sap_chon_va_dem(day), day)
```
Chương trình in `10 [1, 2, 3, 4, 5]`. Biến đếm cho biết đúng số phép so sánh trong mã này, còn không phải số giây chạy. Có thể dùng `perf_counter()` đo thêm, nhưng một phép đo trên năm số quá ngắn để kết luận về xu hướng khi `n` tăng.
Bài luyện
Sắp xếp chọn theo mã trong bài so sánh bao nhiêu lần khi dãy có 5 phần tử?
Đây chỉ là lượt ngoài đầu.
Không phải tổng các lượt.
4+3+2+1=10.
Vòng trong ngắn dần nên không phải 5×5.
Lời giải
Các lượt ngoài có 4, 3, 2, 1 phép so sánh; cộng được 10.
Bài luyện
Với mã sắp xếp chọn trong bài, dãy năm phần tử đã tăng sẵn có bao nhiêu phép so sánh?
Mã vẫn chạy vòng trong.
Chỉ mới tính lượt đầu.
Số lượt vòng trong chỉ phụ thuộc độ dài n=5.
Giá trị ảnh hưởng cập nhật vị trí, không đổi số lượt so sánh.
Lời giải
Ngay cả khi dãy đã sắp, mã vẫn duyệt các cặp cần xét: 4+3+2+1=10 lần.
Bài luyện
Từ `n(n−1)/2` phép so sánh, bậc thời gian của sắp xếp chọn trong bài là gì?
Số so sánh tăng theo n.
Không có bước chia đôi dãy.
Hạng n² chi phối n.
Khai triển được (n²−n)/2, bậc n².
Lời giải
n(n−1)/2 = (n²−n)/2; khi n lớn, hạng n² quyết định bậc O(n²).
Đang học