Selection Sort chia mảng thành 2 phần: phần đã sắp xếp và phần chưa sắp xếp. Lặp lại: tìm phần tử nhỏ nhất từ phần chưa sắp xếp, đổi chỗ với phần tử đầu tiên của phần chưa sắp xếp. Phần đã sắp xếp mở rộng, phần chưa sắp xếp thu hẹp.
Độ phức tạp Selection Sort
- Time Complexity: O(n²)
- Space Complexity: O(1)
Input và Output
Input: Danh sách chưa sắp xếp: 5 9 7 23 78 20 Output: Mảng trước sắp xếp: 5 9 7 23 78 20 Mảng sau sắp xếp: 5 7 9 20 23 78
Thuật toán
selectionSort(array, size)
Input: Mảng dữ liệu, tổng số phần tử
Output: Mảng đã sắp xếp
Begin
for i := 0 to size-2 do
iMin := i
for j := i+1 to size-1 do
if array[j] < array[iMin] then iMin := j
done
swap array[i] with array[iMin]
done
End
Ví dụ (C++)
#include <iostream>
using namespace std;
void swapping(int &a, int &b) { int t=a; a=b; b=t; }
void display(int *a, int n) { for(int i=0;i> n;
int arr[n];
cout << "Nhập phần tử:" << endl;
for(int i=0;i> arr[i];
cout << "Trước: "; display(arr,n);
selectionSort(arr,n);
cout << "Sau: "; display(arr,n);
}
Kết quả
Nhập số phần tử: 6 Nhập phần tử: 5 9 7 23 78 20 Trước: 5 9 7 23 78 20 Sau: 5 7 9 20 23 78
Đặc điểm: Selection Sort không ổn định, in-place, luôn O(n²) bất kể dữ liệu đầu vào. Ưu điểm: số lần swap tối thiểu (n-1 lần). Phù hợp khi ghi bộ nhớ đắt.