*Ý tưởng:
Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành; lúc này dãy hiện hành chỉ còn N-1 phần tử cần sắp xếp, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử.
Dãy ban đầu có N phần tử, vậy tóm tắt ý tưởng giải thuật là thực hiện N-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.
*Giải thuật
Bước 1: i = 1;
Bước 2: Tìm phần tử a[vtmin] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N]
Bước 3: Hoán vị a[vtmin] và a[i]
Bước 4:
i = i+1
Nếu i < N thì lặp lại Bước 2
Ngược lại: Dừng.
Cài đặt
void SelectionSort(int a[],int N )
{
int vtmin;
for(int i=0; i<N-1 ; i++)
{
vtmin = i;
for(int j = i+1; j <N ; j++)
{
if (a[j ] < a[vtmin])
min=j;
}
Hoanvi(a[min], a[i]);
}
}
void Hoanvi(int &a, int &b)
{ int tam=a;
a=b;
b=tam;
}