Sắp xếp chọn
Sắp xếp chọn sắp xếp danh sách giống cách nhiều người xếp bài trên tay: tìm lá nhỏ nhất, đặt lên đầu, rồi tìm lá nhỏ nhất trong số còn lại. Nó thực hiện nhiều phép so sánh nhưng rất ít hoán đổi, và thời gian chạy hầu như không phụ thuộc vào thứ tự danh sách.
Ý tưởng
Chia danh sách thành phần đã sắp xếp ở bên trái, lúc đầu trống, và phần chưa sắp xếp ở bên phải. Quét phần chưa sắp xếp và ghi nhớ vị trí giá trị nhỏ nhất. Hoán đổi giá trị đó với giá trị chưa sắp xếp đầu tiên: phần đã sắp xếp tăng thêm một. Lặp lại cho đến khi chỉ còn một giá trị, chắc chắn là giá trị lớn nhất.
Ví dụ
Lấy 5, 1, 4, 2, 8. Lượt thứ nhất quét cả năm giá trị, thấy 1 là nhỏ nhất và hoán đổi nó với 5: 1, 5, 4, 2, 8. Lượt thứ hai quét 5, 4, 2, 8, thấy 2 và hoán đổi nó với 5: 1, 2, 4, 5, 8. Lượt thứ ba thấy 4 đã đúng chỗ, lượt thứ tư thấy 5 đã đúng chỗ, nên không có gì di chuyển. Tổng cộng 4 + 3 + 2 + 1 = 10 phép so sánh và chỉ 2 lần hoán đổi. Sắp xếp nổi bọt cần 4 lần hoán đổi với cùng danh sách này.
Số phép so sánh luôn như nhau
Để chắc chắn giá trị nào nhỏ nhất, lượt quét phải xem mọi giá trị còn lại. Lượt 1 thực hiện n − 1 phép so sánh, lượt 2 thực hiện n − 2, cứ thế giảm dần đến 1, cộng lại là n(n − 1)/2. Con số này không phụ thuộc vào danh sách: danh sách đã sắp xếp tốn đúng bằng số phép so sánh như danh sách đảo ngược. Sắp xếp chọn không thể dừng sớm, vì một lượt quét thấy giá trị nhỏ nhất đã ở đầu cũng không biết gì thêm về phần còn lại.
Ít hoán đổi
Mỗi lượt hoán đổi nhiều nhất một lần, nên sắp xếp chọn không bao giờ hoán đổi quá n − 1 lần, và bỏ qua lần hoán đổi khi giá trị nhỏ nhất đã đúng chỗ. Sắp xếp nổi bọt và sắp xếp chèn hoán đổi đúng bằng số cặp sai thứ tự, có thể lên tới khoảng n²/2. Khi ghi một giá trị tốn kém hơn nhiều so với đọc hai giá trị, chẳng hạn trên bộ nhớ bị hao mòn sau mỗi lần ghi, số lần hoán đổi ít là một lợi thế.
Không ổn định
Một thuật toán sắp xếp là ổn định khi các giá trị bằng nhau giữ nguyên thứ tự ban đầu. Sắp xếp chọn không ổn định, vì một lần hoán đổi xa có thể đưa một giá trị vượt qua giá trị bằng nó. Với 2, 2, 1, lượt thứ nhất hoán đổi số 2 đầu tiên với 1, được 1, 2, 2 với hai số 2 giờ đã đổi thứ tự cho nhau. Phiên bản dịch chuyển các giá trị ở giữa thay vì hoán đổi thì ổn định, nhưng phải di chuyển nhiều giá trị hơn hẳn.
Tự khám phá
Mở ứng dụng và nhấn Phát, hoặc nhấn Bước để đi từng phép so sánh. Giá trị đang được quét được tô sáng, giá trị nhỏ nhất hiện tại có màu riêng, và mỗi lượt kết thúc bằng một lần hoán đổi vào phần đã sắp xếp ở bên trái. Hãy thử danh sách đã sắp xếp và danh sách đảo ngược: số phép so sánh như nhau, chỉ số lần hoán đổi khác nhau.
Câu hỏi thường gặp
Độ phức tạp thời gian của sắp xếp chọn là bao nhiêu?
O(n²) trong mọi trường hợp: đúng n(n − 1)/2 phép so sánh với n giá trị, bất kể thứ tự. Nó hoán đổi tối đa n − 1 lần và chỉ cần O(1) bộ nhớ phụ.
Sắp xếp chọn khác sắp xếp nổi bọt thế nào?
Sắp xếp nổi bọt hoán đổi các cặp kề nhau trong lúc đi và có thể dừng sớm khi một lượt không có hoán đổi nào. Sắp xếp chọn chỉ ghi nhớ vị trí giá trị nhỏ nhất và hoán đổi một lần ở cuối mỗi lượt. Sắp xếp chọn hoán đổi ít hơn; sắp xếp nổi bọt nhanh hơn với danh sách gần như đã sắp xếp.
Sắp xếp chọn có ổn định không?
Không. Một lần hoán đổi có thể đưa một giá trị vượt qua giá trị khác bằng nó, nên các giá trị bằng nhau có thể đổi thứ tự. Có thể làm nó ổn định bằng cách dịch chuyển thay vì hoán đổi, nhưng phải di chuyển nhiều hơn.
Sắp xếp vun đống liên quan gì đến sắp xếp chọn?
Sắp xếp vun đống là sắp xếp chọn với cách tìm giá trị tiếp theo nhanh hơn: nó giữ phần chưa sắp xếp trong một đống (heap), nên mỗi lần chọn chỉ mất khoảng log n bước thay vì quét toàn bộ. Nhờ đó tổng thời gian giảm xuống O(n log n).
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử sắp xếp chọn