Thuật toán selection sort sắp xếp một mảng bằng cách đi tìm phần tử có giá trị nhỏ nhất(giả sử với sắp xếp mảng tăng dần) trong đoạn đoạn chưa được sắp xếp và đổi cho phần tử nhỏ nhất đó với phần tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng). Thuật toán sẽ chia mảng làm 2 mảng con
- Một mảng con đã được sắp xếp
- Một mảng con chưa được sắp xếp
Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.
Code tham khảo về thuật toán Selection Sort
#include <iostream>
using namespace std;
// Hàm đổi chỗ 2 số nguyên
void swap(int &xp, int &yp)
{
int temp = xp;
xp = yp;
yp = temp;
}
// Hàm selection sort
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// Di chuyển ranh giới của mảng đã sắp xếp và chưa sắp xếp
for (i = 0; i < n-1; i++)
{
// Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên
swap(arr[min_idx], arr[i]);
}
}
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
int i;
cout << "Day so sau khi sap xep: ";
for (i=0; i < size; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printArray(arr, n);
return 0;
}