Hình minh họa cho thuật toán Selection Sort
Chào bạn! Đây là bài viết đầu tiên trong series về các thuật toán sắp xếp và tìm kiếm căn bản của mình. Trong bài viết này, mình sẽ giới thiệu đến bạn thuật toán sắp xếp Selection Sort. Mình sẽ cố gắng trình bày mọi thứ một cách dễ hiểu nhất. Như đã từng có câu nói của Einstein: "Nếu bạn không thể giải thích một vấn đề cho một đứa trẻ 6 tuổi, thì có nghĩa là bạn chẳng hiểu gì về vấn đề đó cả!". Điều đó có nghĩa là nếu bạn không hiểu, thì lỗi không phải do bạn, mà là do cách mình giải thích chưa rõ ràng. Và mình khuyến khích bạn hãy đặt câu hỏi nếu có bất kỳ điều gì bạn không hiểu.
Vấn đề cần giải quyết
Giả sử bạn được cho một dãy số lộn xộn với N phần tử. Bạn sẽ làm thế nào để sắp xếp dãy số này theo thứ tự tăng dần?
Ý tưởng đơn giản nhất
Một ý tưởng đơn giản mà bạn có thể nghĩ ra là:
- Bước 1: Tìm giá trị nhỏ nhất trong dãy số từ vị trí 1 đến N.
- Bước 2: Hoán đổi giá trị nhỏ nhất đó với giá trị ở vị trí đầu tiên của dãy số.
- Bước 3: Lặp lại bước 1 và bước 2, nhưng bắt đầu từ vị trí thứ 2 (vì giờ đây ta đã có giá trị nhỏ nhất ở đầu dãy, nên có thể bỏ qua nó).
Nhận xét: Khi đến bước 3, ta đã thu hẹp bài toán thành dãy số từ 2 đến N. Và cứ tiếp tục thu hẹp dần cho đến khi ta chỉ còn dãy số từ N đến N thì có nghĩa là ta đã hoàn thành sắp xếp. Đây chính là thuật toán Selection Sort. Trên một số tài liệu, code có thể khác nhau, nhưng ý tưởng chung vẫn giống nhau.
Dưới đây là đoạn code mẫu mà mình đã chuẩn bị:
for (int i=0; i arr[j]) {
minPosition = j;
}
}
// Hoán đổi giá trị nhỏ nhất với phần tử ở vị trí i
swap(arr[i], arr[minPosition]);
} Bạn có thể xem chương trình đầy đủ tại đây: https://ideone.com/YGIeFC
Độ phức tạp
Độ phức tạp của thuật toán này là O(N^2) (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ể giải thích ngắn gọn 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 bạn muốn tìm hiểu thêm, 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ư đã thấy ở trên, độ phức tạp của thuật toán là O(N^2). Với hiện nay, máy tính có thể xử lý tầm 10^9 phép tính mỗi giây, thì thời gian để sắp xếp dãy số kích thước N là N^2/10^9 (giây).
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, khi nào bạn nên sử dụng thuật toán này?
- 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 và dễ thực hiện.
- 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ỏ) và không muốn sử dụng các thuật toán phức tạp như QuickSort thì thuật toán Selection Sort là một lựa chọn hợp lý.
Hy vọng bài viết này đã giúp bạn hiểu thêm về thuật toán Selection Sort. Nếu bạn có bất kỳ câu hỏi hoặc ý kiến gì, hãy để lại comment để mình có thể trả lời cho bạn. Chúc bạn thành công trong việc học và ứng dụng thuật toán này!
