Giải thuật sắp xếp lựa chọn (Selection sort)
1. Ý tưởng thuật toán
Trong dãy gồm n phần tử, tìm phần tử nhỏ nhất (min) và đưa nó lên đầu dãy, rồi “lờ” phần tử này đi. Lúc này, dãy hiện hành là phần còn lại sau khi bỏ qua phần tử bị lờ. Tiếp tục tìm phần tử min trong dãy hiện hành gồm n-1 phần tử, rồi lại đưa nó lên đầu và “lờ” nó đi. Lặp lại thao tác cho đến khi dãy đang xét chỉ còn 1 phần tử, cũng chính là phần tử lớn nhất/ nhỏ nhất (tùy vào sắp xếp tăng hay giảm dần).
Ta sử dụng khái niệm nghịch thế để tìm phần tử nhỏ nhất và sắp xếp chúng.
2. Nghịch thế
Cho dãy số a[0], a[1], a[2], …, a[n]. Gọi i, j là các chỉ số của 2 phần tử a[i], a[j]. Nếu có i<j và a[i]>a[j] thì ta gọi đây là 1 nghịch thế.
Để tìm được phần tử min, nhất thiết ta phải so sánh phần tử min với các phần tử còn lại của dãy, rồi đổi chỗ 2 phần tử. Hành động này nhằm hủy nghịch thế.
3. Cơ chế hoạt động
Cho dãy số: | 2 | 5 | 3 | 1 | 4 |. Sắp xếp dãy số tăng dần.
-
Bước 1: Xét dãy hiện hành: | 2 | 5 | 3 | 1 | 4 |
min = 1, đổi chỗ với phần tử đầu của dãy hiện hành, ta được dãy mới: | 1 | 5 | 3 | 2 | 4 | -
Bước 2: Xét dãy hiện hành: | 5 | 3 | 2 | 4 |
min = 2, đổi chỗ với phần tử đầu của dãy hiện hành, ta được dãy mới: | 2 | 3 | 5 | 4 | -
Bước 3: Xét dãy hiện hành: | 3 | 5 | 4 |
min = 3, đổi chỗ với phần tử đầu của dãy hiện hành, ta được dãy mới: | 3 | 5 | 4 | -
Bước 4: Xét dãy hiện hành: | 5 | 4 |
min = 4, đổi chỗ với phần tử đầu của dãy hiện hành, ta được dãy mới: | 4 | 5 | -
Bước 5: Xét dãy hiện hành: | 5 |
min = 5, cũng chính là phần tử cuối cùng và lớn nhất, kết thúc.
Dãy ban đầu sau khi thực hiện thuật toán: | 1 | 2 | 3 | 4 | 5 |
4. Các bước của thuật toán
Dãy gồm n phần tử
- Bước 1: i = 0;
- Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]
- Bước 3: Đổi chỗ a[min] và a[i]
- Bước 4:
+Nếu i < n - 1 thì i = i + 1; Lặp lại Bước 2;
+Ngược lại: Dừng.
5. Cài đặt (C++)
void selectionSort(int a[], int n) {
int min; //dùng để lưu vị trí phần tử nhỏ nhất
for (int i = 0; i < n - 1; i++) {
min = i;
for(int j = i + 1; j < n; j++)
if(a[j] < a[min])
min = j;
int t = a[i];
a[i] = a[min];
a[min] = t;
}
}
4. Độ phức tạp của thuật toán
Mỗi bước i luôn cần n - i so sánh để tìm phần tử nhỏ nhất ở dãy hiện hành. Biểu thức tính n - i không phụ thuộc vào tình trạng của dãy đã cho, do đó, trong mọi trường hợp ta có độ phức tạp của thuật toán là:
Mỗi một hoán vị dùng 3 phép gán. Số phép gán lại phụ thuộc vào trạng thái ban đầu của dãy đã cho. Do đó ta chỉ có thể ước lượng trong 2 tình huống:
- Tốt nhất: số lần so sánh là n(n-1)/2, số phép gán là 0.
- Xấu nhất: số lần so sánh là n(n-1)/2, số phép gán là 3n(n-1)/2
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?