Insertion sort is a simple comparison sorting algorithm, that considers at a step k, the elements of the array A[0,k-1] are already sorted out, and the element on the k position will be inserted that way that after the insertion, the elements A[0,k] are sorted out.
Inserting the k element in the A[0,k-1] sequence requires a few steps:
- the element must be retained in a temporal variable;
- moving all the elements from the A[0,k-1] array that are greater than A[k] with a position to the right (this presumes a run from right to left of the array);
- placing the A[k] element on the former spot of the last element that moved.
Step by step example :
Having the following list, let’s try to use insertion sort to arrange the numbers from lowest to greatest:
Unsorted list: 6 4 5 10 3 1 8 9 7 2
Step 1:
4 6 5 10 3 1 8 9 7 2 – As 6 was the first element, at step 1, the element 4 is being inserted, and 4 is smaller than 6, so it must place before 6, so the order would be 4 6.
Step 2:
4 5 6 10 3 1 8 9 7 2 – At step 2, 5 was the element to be inserted, and being smaller than 6, it goes before it, but then it is compared to 4 which is smaller than 5, now the order would be 4 5 6.
Step 3:
4 5 6 10 3 1 8 9 7 2 – At step 3, 10 was the new element, and being greater than 6, the element was in the right place and no moving had to take place, now the order would be 4 5 6 .
Step 4:
3 4 5 6 10 1 8 9 7 2 – At step 4, 3 was the new element, and compared to 10 it is smaller, so it has to move to the left, also, it is compared to 6 then to 5 and then to 4, and is smaller than any of these, so the position of the element 3 is at the left of all these numbers, now the order would be 3 4 5 6.
Step 5:
1 3 4 5 6 10 8 9 7 2 – Step 5, the new element is 1, which is again smaller than 10, then like in the previous steps, it is compared to the next numbers 6,5,4,3 and is smaller than an of these, so it ends at the left of the array that has been sorted out so far, with the order being 1 3 4 5 6
Step 6:
1 3 4 5 6 8 10 9 7 2 – At step 6, the element 8 was compared to 10 and moved to the left, but compared to 6 it is greater, so now the list would look like 1 3 4 5 6 8
Step 7:
1 3 4 5 6 8 9 10 7 2 – Step 7, the element 9 was compared to 10 and moved to the left having it being smaller, but it is greater than 8 so the list is : 1 3 4 5 6 8 9
Step 8:
1 3 4 5 6 7 8 9 10 2 – Step 8, the element of 7 was compared to 10, so it had to move to the left of 10, also 7 is smaller than 8 which it moves another position to the left, but it is greater than 6, so it found its position, with the array looking like : 1 3 4 5 6 7 8 9
Step 9:
1 2 3 4 5 6 7 8 9 10 – At the final step 9, the element 2 was compared to 10, being smaller it moves to the left, then again it is compared to 9, then 8, 7, 6, 5, 4, 3 and is smaller than any of these numbers, so the right position is to the left, but being greater than 1, it’s at one position to the right of the element 1, now the final order is the right one : 1 2 3 4 5 6 7 8 9 10
Having no more elements to compare 10 to, the algorithm now knows that the list is sorted.
Sample code:
#include < iostream >using namespace std;
int main(void)
{int i;
long int A[100];
long int n=100;
cout << "Please insert the number of elements to be sorted: ";
cin >> n; // The total number of elements
for(int i=0;i < n;i++)
{cout << "Input " << i << " element: ";
cin >> A[i]; // Adding the elements to the array
}cout << "Unsorted list:" << endl; // Displaying the unsorted array
for(int i=0;i < n;i++)
{cout << A[i] << " ";
}for (int k=1;k < n;k++)
{int temp=A[k]; // the k element to be inserted is retained in a temporal variable,
i = k-1; //at first it is the A[1] value, which is the second value of the array
while (i >=0 && A[i] > temp)
{A[i+1] = A[i];
i = i-1;
}A[i+1] = temp;
}cout << "Sorted list:" << endl; // Displaying the sorted array
for(int i=0;i < n;i++)
{cout << A[i] << " ";
}return 0;
}
Output:
Code explanation:
for (int k=1;k < n;k++)
{int temp=A[k];
i = k-1;
while (i >=0 && A[i] > temp)
{A[i+1] = A[i];
i = i-1;
}A[i+1] = temp;
}
The temp variable retains the value to be inserted, which at the first run of the loop would be A[1], being the second value as A[0] is the first value. Then the while loop checks to see if A[0] is greater than A[1], and if it is true, a swap between the values takes place. Also, i is decremented by 1. At the next run, A[2] is compared to A[1], and if it is greater a swap takes place, and after that it is compared to A[0], and if its greater there is a swap between the values, if not, the proper order has been found out.
Complexity:
How many compares are done? 1+2+…+(n-1) which results in O(n^2) worst case and (n-1)* 1 which is O(n) on best case. Also, how many element shifts are done? 1+2+…+(n-1) on O(n^2) worst case and 0 , O(1) best case.
Advantages:
- it is easy to learn;
- few lines of code;
- efficient for small data sets;
- stable, does not change the relative order of elements with equal keys;
Disadvantages:
- not effective for large numbers of sorting elements;
- needs a large number of element shifts;
- as the number of elements increases the performance of the program would be slow.
Conclusion:
Like bubble sort, insertion sort is also a simple comparison algorithm. Unfortunately, it is not quite efficient on large lists, but it is an easy sorting algorithm to learn. The best case would be that the list was already sorted, meaning it would only have to traverse the list as oppose to traverse and swap. Worst case is achieved because regardless it has to traverse as well as swap through the entire list.
