Selection Sort

[trieu.dev.da]

Ý tưởng đơn giản nhất
có thể nghĩ ra là:

• Bước 1. Đầu tiên, mình sẽ tìm ra giá trị nhỏ nhất của dãy số từ vị trí 1..N.
• Bước 2. Sau đó, đổi chỗ giá trị nhỏ nhất đó cho vị trí đầu tiên của dãy.
• Bước 3. Lặp lại bước 1 và bước 2, nhưng là từ vị trí số 2 (vì giờ đây ta đã có giá trị đầu tiên là giá trị nhỏ nhất rồi, nên có thể bỏ qua nó).

Nhận xét: Mình để ý rằng, khi đến bước 3, thực sự ta đã thu hẹp được bài toán. Từ dãy số 1..N, giờ đây chỉ còn 2..N. Và cứ như thế thì ta cứ thu hẹp dần cho đến N..N thì coi như xong. Và đây chính là thuật toán selection sort.
Trên một số tài liệu có thể code sẽ khác, nhưng nhìn chung vẫn là ý tưởng đó nhưng lại diễn giải theo một cách khác mà thành.
Độ phức tạp
của thuật toán này là: O(N2)O(N2)
(Nếu bạn chưa biết cách để xác định độ phức tạp của một thuật toán thì mình có thể nói sơ qua là: số lượng phép gán và so sánh được dùng để xây dựng thuật toán. Nếu các bạn muốn tìm hiểu thêm, xin hãy để lại comment, để mình có thể viết bài về cách đánh giá độ phức tạp của thuật toán này).
Ứng dụng
Như ta đã thấy ở trên, độ phức tạp thuật toán là: O(N2)O(N2)
Ta có thể hình dung: Máy tính đời nay có thể xử lý tầm 109109 phép tính/giây, thì thời gian để sắp xếp dãy số kích thước N là: N2/109N2/109 (s).
Dưới đây là bảng ví dụ về thời gian chạy của thuật toán này:

N	Time
100	0,00(s)
10.000	0,10(s)
1.000.000	1.000(s)
100.000.000	10.000.000(s)

Với độ phức tạp cao như vậy thì lúc nào ta nên sử dụng nó?

• Khi bạn cần sắp xếp một dãy các phần tử có kích thước nhỏ (tầm 50-100 phần tử) thì đây là một thuật toán dễ hiểu, dễ implement.
• Khi bạn chỉ cần lấy K số nhỏ nhất (hoặc lớn nhất) đầu tiên của dãy. Nếu bạn chỉ cần lấy K phần tử nhỏ nhất đầu tiên của dãy (với K và N nhỏ) mà lại dùng đến các thuật toán to bự như: QuickSort thì thật là không nên.