Thuật toán InterchangeSort

*Ý tưởng 

Ý tưởng chính của giải thuật là xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. 

Giải thuật

*Bước 1 : i = 1;// bắt đầu từ đầu dãy

*Bước 2 : j = i+1;//tìm các phần tử a[j] < a[i], j>i

*Bước 3 :

  Trong khi j <= N thực hiện

  Nếu a[j]<a[i]: Hoán vị a[i], a[j];

  j = j+1; 

*Bước 4 : i = i+1;

  Nếu  i < N: Lặp lại Bước 2.

  Ngược lại:  Dừng. 

Cài đặt

void InterchangeSort(int a[], int N )

{  int  i,j;

  for (i = 0 ; i<N-1 ; i++)

  for (j =i+1; j < N ; j++)

  if(a[j ]< a[i])

  Hoanvi(a[i],a[j]);

}

  void Hoanvi(int &a, int &b)

  {

  int tam=a;

  a=b;

  b=tam;

  }