Insertion Sort is a way of sorting elements. While using insertion sort, we traverse from right to left element.
Steps :
1. Assume 0th element is already sorted.
2. Starting i from first element till last :
- In a loop(j ), check if the previous element is greater than the comparing element( for example for first time, we will be comparing 1st element to 0th element.)
- If previous element is greater than comparing element, we will replace the j+1th element with j.[Remember before doing this keep array[i] stored in some variable, as it will be compared to all elements].
- when loops finished, just replace the last index element with array[i] stored value.
Code :
for(i =1; i{
int val = arr[i];
int j = i-1;
while( j >=0 && A[j] > val)
{
A[j+1] = A[j];
j--;
}
A[j] = val;
}
Steps :
1. Assume 0th element is already sorted.
2. Starting i from first element till last :
- In a loop(j ), check if the previous element is greater than the comparing element( for example for first time, we will be comparing 1st element to 0th element.)
- If previous element is greater than comparing element, we will replace the j+1th element with j.[Remember before doing this keep array[i] stored in some variable, as it will be compared to all elements].
- when loops finished, just replace the last index element with array[i] stored value.
Code :
for(i =1; i
int val = arr[i];
int j = i-1;
while( j >=0 && A[j] > val)
{
A[j+1] = A[j];
j--;
}
A[j] = val;
}