Thuật toán sắp xếp chọn - Selection Sort
Sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất (xét theo thứ tự tăng dần) từ phần chưa được sắp xếp và đặt nó ở đầu. Thuật toán duy trì hai mảng con trong một mảng nhất định.
1) Mảng con đã được sắp xếp.
2) Mảng con còn lại chưa được sắp xếp.
Trong mỗi lần lặp lại sắp xếp lựa chọn, phần tử nhỏ nhất (xét theo thứ tự tăng dần) từ mảng con chưa được sắp xếp sẽ được chọn và chuyển đến mảng con đã sắp xếp.
Diễn giải một cách đơn giản hơn thì thuật toán sắp chọn diễn ra như sau:
- Tìm phần tử nhỏ nhất đưa vào vị trí 1
- Tìm phần tử nhỏ thứ 2 đưa vào vị trí 2
- Tìm phần tử nhỏ thứ 3 đưa vào vị trí 3
- ....
- Tìm phần tử nhỏ thứ n đưa vào vị trí n trong mảng
Ví dụ sau giải thích các bước trên:
arr [] = 64 25 12 22 11 // Tìm phần tử nhỏ nhất trong arr [0 ... 4] // và đặt nó ở đầu 11 25 12 22 64 // Tìm phần tử nhỏ nhất trong arr [1 ... 4] // và đặt nó ở đầu arr [1 ... 4] 11 12 25 22 64 // Tìm phần tử nhỏ nhất trong arr [2 ... 4] // và đặt nó ở đầu arr [2 ... 4] 11 12 22 25 64 // Tìm phần tử nhỏ nhất trong arr [3 ... 4] // và đặt nó ở đầu arr [3 ... 4] 11 12 22 25 64
Ví dụ sắp xếp chọn trong C++
Hàm xử lý sắp xếp chọn
void selectionSort(int arr[], int n)
{
int i, j, min_index;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_index = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_index])
min_index = j;
// Swap the found minimum element with the first element
swap(&arr[min_index], &arr[i]);
}
}
Phân tích thuật toán
- Best Case: 0 đổi chỗ (n-1 như trong đoạn mã), 
/2 so sánh.
- Worst Case: n-1 đổi chỗ và 
/2 so sánh
- Average Case: O(n) đổi chỗ và 
/2 so sánh.
Ưu điểm nổi bật của sắp xếp chọn là số phép đổi chỗ ít. Điều này có ý nghĩa nếu như việc đổi chỗ là tốn kém.
إرسال تعليق