Tổng quan
Selection Sort xây dựng mảng đã sắp xếp từng phần tử một. Mỗi lượt nó quét phần chưa sắp, tìm giá trị nhỏ nhất còn lại và hoán đổi nó vào vị trí đã sắp kế tiếp.
Selection Sort hoạt động thế nào?
- Coi toàn mảng là chưa sắp và trỏ tới chỉ số đầu tiên.
- Quét phần chưa sắp để tìm chỉ số của giá trị nhỏ nhất.
- Hoán đổi giá trị nhỏ nhất đó vào vị trí hiện tại, mở rộng phần đã sắp thêm một phần tử.
- Tiến sang vị trí kế tiếp và lặp lại cho đến khi mảng được sắp xếp.
Khi nào nên dùng?
- Khi cần giảm thiểu chi phí ghi/hoán đổi — nó thực hiện tối đa n−1 lần hoán đổi.
- Mảng nhỏ hoặc để giảng dạy, khi hành vi đơn giản, dễ dự đoán là lợi thế.
Phân tích độ phức tạp
Selection Sort luôn quét toàn bộ phần chưa sắp, nên chạy O(n²) trong mọi trường hợp, không có dừng sớm. Ưu điểm là số lần hoán đổi tối thiểu O(n). Nó tại chỗ (O(1) bộ nhớ) nhưng ở dạng mảng thông thường thì không ổn định.
Câu hỏi thường gặp
Selection Sort khác Bubble Sort thế nào?
Cả hai đều O(n²), nhưng Selection Sort thực hiện ít hoán đổi hơn nhiều (một lần mỗi lượt) nhờ chọn phần tử nhỏ nhất, trong khi Bubble Sort hoán đổi liên tục trong mỗi lượt.