Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Mỗi lượt tìm số nhỏ nhất
Mảng chia hai bởi một ranh giới: bên trái đã sắp xếp, bên phải chưa. Mỗi lượt tìm số nhỏ nhất bên phải, đưa về sát ranh giới, rồi đẩy ranh giới sang một bước.
[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8] → [1, 2, 4, 5, 8]
Ranh giới chạy dần sang phải
- Lượt 1Cả mảng chưa sắp: 5 1 4 2 8. Nhỏ nhất là 1, đưa lên đầu
- Lượt 2Đã sắp: 1. Còn 5 4 2 8, nhỏ nhất là 2
- Lượt 3Đã sắp: 1 2. Còn 4 5 8, nhỏ nhất là 4, đã đúng chỗ
- XongRanh giới chạm cuối mảng. Mỗi lượt tốn tối đa một lần đổi chỗ
Trường hợp xấu nhất, so sánh bằng nhau
| Thuật toán | So sánh | Đổi chỗ |
|---|---|---|
| Bubble | n²/2 | -tới n²/2 |
| Selection | n²/2 | +n-1 |
Mảng đã đúng thứ tự thì sao
Bubble sort có cờ dừng sớm nên chỉ tốn n-1 phép so sánh rồi dừng. Selection sort vẫn quét đủ n²/2 lần, vì nó không có cách nào biết mảng đã xong từ trước.
Khi nào chênh lệch đó là thật
Phép ghi đắt hơn phép so sánh khi phần tử lớn, hoặc khi phải ghi xuống đĩa. Lúc đó n-1 lần đổi chỗ thắng rõ, dù big-O của hai bên viết giống hệt nhau.
Selection sort: được gì, mất gì
Ưu điểm
Đúng n-1 lần đổi chỗ, ít nhất nhóm cơ bản
Sắp xếp tại chỗ, không cần bộ nhớ phụ
Thời gian chạy đoán được, không phụ thuộc dữ liệu
Nhược điểm
Luôn n² so sánh, kể cả mảng đã đúng sẵn
Không có dừng sớm, mảng gần đúng cũng vậy
Bản đổi chỗ không ổn định
Lưu lại để chạy tay sau
Loạt bài thuật toán sắp xếp cho dev Việt Nam.
