Thuật toán sắp xếp lựa 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 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 được đưa vào vị trí 1
- Tìm phần tử nhỏ thứ 2 được đưa vào vị trí 2
- Tìm phần tử nhỏ thứ 3 được đưa vào vị trí 3
- Tìm phần tử nhỏ thứ n được đư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 lựa chọn trong C++
Hàm sắp xếp các lựa chọn sắp xếp
void selectionSort [ int mảng[], < int n]
{
int i, j, min_index;
// Di chuyển từng ranh giới của mảng con chưa sắp xếp
cho [i = 0 ; i < n 1; i++]
{
// Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp
min_index = i;
cho [j = i+ 1 ; j