Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Ranh giới chạy dần sang phải
- TìmTìm số nhỏ nhất trong cả mảng
- ĐặtĐưa số đó về vị trí đầu tiên
- Thu hẹpVị trí đầu xong rồi, không xét lại nữa
- LặpLàm lại với phần còn lại bên phải
So sánh và ghi là hai chi phí
So sánh là đọc hai số để biết số nào nhỏ hơn. Ghi là gán một giá trị vào mảng. Ghi thường tốn hơn đọc, nhất là khi mỗi phần tử lớn hoặc phải ghi xuống đĩa.
Con số đáng nhớ
Selection sort đổi chỗ đúng n-1 lần
Cùng nhóm, khác chỗ tốn
| Thuật toán | So sánh | Đổi chỗ |
|---|---|---|
| Bubble sort | n² | -tới n²/2 |
| Selection sort | n² | +đúng n-1 |
Đổi lại thì mất gì
Selection sort không có cờ dừng sớm. Mảng đã đúng thứ tự sẵn thì nó vẫn quét hết để tìm số nhỏ nhất. Thời gian chạy vì thế luôn giống nhau, dù dữ liệu thế nào.
Selection sort được gì, mất gì
Ưu điểm
Đổi chỗ đúng n-1 lần, í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 trước được
Nhược điểm
Luôn n² phép so sánh, kể cả mảng đúng sẵn
Không có dừng sớm
Bản đổi chỗ không ổn định
Bài sau: insertion sort
Cái duy nhất trong nhóm n² vẫn chạy thật trong thư viện chuẩn.
