Elementary Sorts — minh họa tương tác
Bubble · Selection · Insertion — ba thuật toán O(n²) kinh điển. Xem từng phép so sánh và swap, so sánh số phép toán, và kiểm chứng tính ổn định (stability).
1. Sort animator
Chọn thuật toán, bấm Step để đi từng bước hoặc Play để chạy tự động. Vàng = đang so sánh, đỏ = đang swap, xanh = đã đúng vị trí.
2. So sánh 3 thuật toán
Chạy cùng một mảng qua cả ba thuật toán, đếm số phép so sánh + swap/shift và vẽ bar chart. Thử mảng đã-sorted vs ngẫu nhiên để thấy khác biệt.
| Thuật toán | So sánh | Swap / Shift | Tổng phép | Ổn định? |
|---|
Cùng O(n²) nhưng số phép thực tế khác rõ theo loại đầu vào: trên mảng đã sorted, bubble & insertion về O(n), selection vẫn O(n²) so sánh.
3. Stability demo
Mảng gồm các cặp (khóa, nhãn) với khóa trùng nhau. Sort theo khóa — kiểm tra thứ tự tương đối của các nhãn cùng khóa có được giữ không.
Selection sort không ổn định: cú swap "nhảy xa" có thể ném một phần tử qua khỏi phần tử cùng khóa đứng trước nó. Bubble & insertion chỉ swap/dịch cặp kề (dùng > chứ không >=) nên giữ thứ tự.