Skip to main content

Insertion sort: Sorting algorithms explained

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.



Comments

Popular posts from this blog

Selection sort: Sorting algorithms explained

In previous post, I discussed about  insertion sort . Now I am going to discuss about selection sort. Selection sort is based on selection. You are given an array, you select the minimum element and place it. For example, let us consider an array: [1,3,2,4,6,5] In selection sort, 1. select the minimum and place it at first position: So, the minimum is 1, now array looks like: 1    3,2,4,6,5 2. select the minimum and place it at the second position. The minimum is 2, now array will look like: 1,2      3,4,6,5 On each step, add the minimum element to the sorted array. In this you keep on going and finally get the whole array sorted. The heart of selection sort is:                 int min_index = i; for (int j = i; j < n; ++j) { if ( array[min_index] > array[j] ) { min_index = j; } } if ( i != min_index ) { int temp = array[i]; array[i] = array[min_in...

Merge sort: Sorting algorithms explained

For me, merge sort is quite complex. It requires dividing the list to be sorted in smaller parts and then merging them. It works on divide and conquer philosophy. For example, let us consider an array of 10 elments: int array[] = {2,3,1,4,5,4,2,3,12,10}; In divide section, you will divide in such a way that in every divided part, there are only one element: void divide(int array[],int l,int r) { if ( l != r ) { int mid = ( l + r ) / 2; divide(array,l,mid); divide(array,mid+1,r); merge(array,l,r); } } We start dividing it by middle element. Now, we will merge them: void merge(int array[],int l,int r) { int A[10]; int B[10]; int mid = ( l + r ) / 2; int j = 0; int i; for (i = l; i <= mid; ++i) { A[j++] = array[i]; } j = 0; for (i = mid + 1; i <= r; ++i) { B[j++] = array[i]; } int k = l; for (i = 0,j=0; i <= mid - l && j <= r - mid -1;) { ...