Thuat Toan InsertionSort

Ý tưởng:
Giả sử có dãy a0, a1,…,ai-1 đã được sắp xếp. Ý tưởng của thuật toán là chèn thêm phần tử mới ai vào vị trí thích hợp của đoạn a1…ai-1 sao cho được dãy mới a1…ai đã được sắp xếp
Nguyên tắc sắp xếp như sau: đoạn gồm phần tử a0 đã được sắp xếp, thêm a1 vào được a0,a1 đã được sắp xếp, tiếp tục thêm a2 vào được a0, a1, a2 đã sắp xếp…tiếp tục để thêm an vào để được a0,a1,…,an đã sắp xếp.

Thuật toán:
Đầu vào: n – số phần tử mảng
a – mảng chứa các phần tử bất kỳ
Đầu ra: a- mảng đã được sắp xếp tăng dần
Bước 1: i=1 //giả sử a[0] đã được sắp xếp
Bước 2: tìm vị trí pos thích hợp trong đoạn từ a[0] đến a[i-1] để chèn a[i] vào
Bước 3: đổi chỗ các phần tử từ a[pos] đến a[i-1] sang phải một vị trí để được vị trí chèn a[i] vào
Bước 4: chèn a[i] vào vị trí pos tìm được bằng cách gán a[pos]=a[i]
Bước 5: i=i+1
Nếu i lặp lại bước 2
Ngược lại => Dừng thuật toán

Ví dụ: Cho dãy số a = 12 , 2 , 8 , 5 , 1 ,  6 , 4 , 15
Mô tả các bước chạy khi thực hiện thuật toán với dãy trên :
i=1 => Cần chèn phần tử a[1] vào dãy a[0] => pos=-1
Vi tri so pos=pos+1

i=2 => Cần chèn phần tử a[2] vào dãy a[0],a[1] => pos=1

i=3 => Cần chèn phần tử a[3] vào dãy a[0],a[1],a[2]=> pos = 1

i=4 => Cần chèn phần tử a[4] vào dãy a[0],a[1],a[2],a[3] => pos = 0

i=5 => Cần chèn phần tử a[5] vào dãy a[0],a[1],a[2],a[3],a[4] => pos = 3

i=6 => Cần chèn phần tử a[6] vào dãy a[0],a[1],a[2],a[3],a[4],a[5] => vi tri 2

i=7 => Cần chèn phần tử a[7] vào dãy a[0],a[1],a[2],a[3],a[4],a[5],a[6] => pos = 7

=> dừng
Vậy dãy đã sắp xếp là a = 1 2 4 5 6 8 12 15


Cài đặt:
void InsertionSort(float a[],int n)
{
 float temp;
 for(int i=2;i<=n;i++)
  {
   temp=a[i];
   int vt=i;
   while ((a[vt-1]>temp)&&(vt>1))
    {
     a[vt]=a[vt-1];
     vt=vt-1;
    }
   a[vt]=temp;
  }
}