In the previous post, I discussed about selection sort. In this post, I will be talking about insertion sort.
What does insertion mean? It means to place something somewhere, to insert something at some place.
So basically, it's about placing an element at its sorted position. We have already a sorted array, and we need to place the ith element at its corresponding position.
So, the heart of insertion sort is:
int key = array[i];
int j = i-1;
while (j >= 0 && array[j] > key)
{
array[j+1] = array[j];
j = j-1;
}
array[j+1] = key;
Start from ith element, look for it's suitable position and place the element right there.
A full working code is as follows:
#include <stdio.h>
int main(int argc, char const *argv[])
{
int array[] = {1,2,3,4,10,123,1,8,9};
int n = 9;
for (int i = 1; i < n; ++i)
{
int key = array[i];
int j = i-1;
while (j >= 0 && array[j] > key)
{
array[j+1] = array[j];
j = j-1;
}
array[j+1] = key;
}
for (int i = 0; i < n; ++i)
{
printf("%d\n", array[i]);
}
return 0;
}
Time complexities:
Best case:
Best case occurs when array is already sorted. The complexity in this case is O(n).
Worst case:
It occurs when array is inversely sorted. The complexity is O(n*n) in this case.
Characteristics of insertion sort:
1. This can be used where array is partially sorted.
2. This algorithm is efficient for smaller data set, but highly inefficient for larger data set.
What does insertion mean? It means to place something somewhere, to insert something at some place.
So basically, it's about placing an element at its sorted position. We have already a sorted array, and we need to place the ith element at its corresponding position.
So, the heart of insertion sort is:
int key = array[i];
int j = i-1;
while (j >= 0 && array[j] > key)
{
array[j+1] = array[j];
j = j-1;
}
array[j+1] = key;
Start from ith element, look for it's suitable position and place the element right there.
A full working code is as follows:
#include <stdio.h>
int main(int argc, char const *argv[])
{
int array[] = {1,2,3,4,10,123,1,8,9};
int n = 9;
for (int i = 1; i < n; ++i)
{
int key = array[i];
int j = i-1;
while (j >= 0 && array[j] > key)
{
array[j+1] = array[j];
j = j-1;
}
array[j+1] = key;
}
for (int i = 0; i < n; ++i)
{
printf("%d\n", array[i]);
}
return 0;
}
Time complexities:
Best case:
Best case occurs when array is already sorted. The complexity in this case is O(n).
Worst case:
It occurs when array is inversely sorted. The complexity is O(n*n) in this case.
Characteristics of insertion sort:
1. This can be used where array is partially sorted.
2. This algorithm is efficient for smaller data set, but highly inefficient for larger data set.
Comments
Post a Comment