Insertion sort
In this sorting (ascending order considered) first we take the first element, since there is only one number is there so we consider it is sorted. Then we copy the second element in a temporary variable and compare it with the element at the first position of the array, if the first element is bigger than the element stored in the temporary variable we copy the first element in the second position, the value in the temporary variable is copied at the first position of the array. Now we will take the third element copy it in the temporary variable, we have to go on copying the elements of the array from second position to third position; first position to second position and so on as long as the array elements are bigger than the element stored in the temporary variable. At the end of this process the element stored in the temporary variable is copied in the empty cell. This process continues till (n-1) times.
Insertion Sort:Let us take the following example we will sort the array in ascending order using insertion sort-
2 |
-3 |
5 |
0 |
9 |
6 |
-7 |
4 |
1 |
8 |
First three passes are given in the above figure, there will be (n-1) passes. In this case the array wolud be sorted from the beginning as shown by highlighting the cells.
If we shift the numbers in the array when they are smaller than the numbers stored in the temporary variable (t) then the array would be sorted in descending order.
Program-71
#include <iostream.h>
void insertionSort(int a[], int n){
In the function insertionSort() the first loop counts number of passes, there are (n-1) passes.
int i, j, t;
for(i=1; i<=n-1; i++){
t=a[i];
j=i-1;
while(j>=0 && a[j]>t){
a[j+1]=a[j];
j--;
}
j++;
a[j]=t;
}
}
void main(){
int a[10], i;
for(i=0; i<= 9; i++){
cout<<"Enter the element :"<<i+1<<":";
cin>>a[i];
}
insertionSort(a,10);
cout<<"The sorted array is as under:\n";
for(i=0; i<=9; i++){
cout<<a[i]<<" ";
}
}