Ví dụ: Ta cần sắp mảng sau gồm các phần tử 4 3 2 10 12 1 5 6
Một ví dụ khác: Ta cần sắp xếp mảng gồm các phần tử 12 11 13 5 6
12 , 11, 13, 5, 6
Chúng ta hãy lặp cho i = 1 (phần tử thứ hai của mảng) đến 4 (phần tử cuối cùng của mảng)
i = 1. Vì 11 nhỏ hơn 12, hãy di chuyển 12 và chèn 11 trước 12
11, 12 , 13, 5, 6
i = 2. 13 sẽ vẫn ở vị trí của nó vì tất cả các phần tử trong A [0..I-1] đều nhỏ hơn 13
11, 12, 13 , 5, 6
i = 3. 5 sẽ di chuyển về đầu và tất cả các phần tử khác từ 11 đến 13 sẽ di chuyển trước một vị trí so với vị trí hiện tại của chúng.
5, 11, 12, 13 , 6
i = 4. 6 sẽ di chuyển đến vị trí sau 5, và các phần tử từ 11 đến 13 sẽ di chuyển trước một vị trí so với vị trí hiện tại của chúng.
5, 6, 11, 12, 13
Ví dụ sắp xếp chèn trong C++
Hàm sắp xếp chèn
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, j, last;
for (i = 1; i < n; i++)
{
last = arr[i];
j = i;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j > 0 && arr[j-1] > last)
{
arr[j] = arr[j-1];
j = j – 1;
}
arr[j] = last;
}
}
