Ý tưởng
Cho dãy ban đầu a1 , a2 ,... ,an, ta có thể xem như đã có đoạn gồm một phần tử a1 đã được sắp, sau đó thêm a2 vào đoạn a1 sẽ có đoạn a1 a2 được sắp; tiếp tục thêm a3 vào đoạn a1 a2 để có đoạn a1 a2 a3 được sắp; tiếp tục cho đến khi thêm xong aN vào đoạn a1 a2 ...aN-1 sẽ có dãy a1 a2 .... aN được sắp.Thuật toán
Bước 1: i = 2; // giả sử có đoạn a[1]đã được sắp
Bước 2: x = a[i];
Tìm vị trí posthích hợp trong đoạn a[1] đến a[i-1] để
chèn a[i] vàoBước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i]
Bước 4: a[pos] = x; // có đoạn a[1]..a[i] đã được sắp
Bước 5: i = i+1;
Nếu i ≤N : Lặp lại Bước 2.
Ngược lại : Dừng.
Cài đặt
void InsertionSort(int a[], int N )
{
int pos;
int x; //lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
for(int i=1 ; i<N ; i++) //đoạn a[0] đã sắp
{
x = a[i]; pos = i-1;
// tìm vị trí chèn x
int x; //lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
for(int i=1 ; i<N ; i++) //đoạn a[0] đã sắp
{
x = a[i]; pos = i-1;
// tìm vị trí chèn x
while((pos >= 0)&&(a[pos] > x))
{// kết hợp dời chỗ các phần tử
{// kết hợp dời chỗ các phần tử
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;// chèn x vào dãy
}
pos--;
}
a[pos+1] = x;// chèn x vào dãy
}