Thuật toán SelectionSort

*Ý 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;

}