Insertion sort in C

Sorting - Sorting refers to different techniques or methods of arranging or ordering things based on a criteria.

For example - We have list of student names and their age. Sorting techniques can be applied to sort this list based on student's names in decreasing order or in increasing order of their age or vice versa.

Sorting algorithms are the fundamental algorithm problems in computer science. The sorting algorithms are also embedded into other algorithms like search and merge algorithms.

Some of the sorting algorithms are bubble sort, selection sort, insertion sort, heap sort, quick sort, merge sort etc.

Insertion Sort -  Simple sorting algorithm which works the same way as we play bridge. Cards are laid down on the table facing down and we pick one card at a time compare it with the other cards (from left to right or vice versa) and insert it into the correct position. This sorting algorithm is very easy to implement and is quite efficient for small data set. In fact this algorithm is more efficient than selection sort and bubble sort.

Basic Principle - In every iteration this algorithm removes one element from the data set, compare it with already sorted list of elements and insert it into the correct position. The element to be picked from the input data set can be decided arbitrarily.

How it works with example -

Suppose we have an input array of five elements - 4 2 5 9 1

After each iteration this input array will be divided into two sub arrays. One will be sorted array and other unsorted one. In the beginning our sorted array will have only one element i.e. first element (4 here). Since sorted array has only 1 element it is sorted. Now in the next step we will pick next element i.e. 2 (from the unsorted array). Please follow following steps -

Step 1 :Sorted array in the beginning - 4     Unsorted array in the beginning - 2 5 9 1

Step 2 :Sorted array will become - 2 4        Unsorted array will become - 5 9 1 // here 2 is picked  from  unsorted array and inserted into sorted array after comparing it with already present element 4 in that array.

Step 3 :sorted array will become - 2 4 5      Unsorted array will become - 9 1   //here 5 is picked from unsorted array and inserted into sorted array after comparing it with already present elements 2 and 4 in that array.

Step 4 :sorted array will become - 2 4 5 9    Unsorted array will become - 1    //here 9 is picked from unsorted array and inserted into sorted array after comparing it with already present elements 2, 4 and 5 in that array.

Step 5 :sorted array will become - 1 2 4 5 9   //here 1 is picked from unsorted array and inserted into sorted array after comparing it with already present elements 2, 4, 5 and 9 in that array.

C Code (Insertion Sort) -

#include<stdio.h>
int main(){
  int i,current_position,back_position,array_size,temp,array[20];
 
  printf("\nEnter number of elements to sort:\t ");
  scanf("%d",&array_size);
 
  printf("\nEnter Elements one by one press enter after every element:");
  for(i=0;i<array_size;i++)
  {
  scanf("%d",&array[i]);
  }
 
  printf("\nArray before sorting:");
  for(i=0;i<array_size;i++)
  {
  printf("  %d\t",array[i]);
  }
 
  for(current_position=1;current_position<array_size;current_position++)
  {
  back_position = current_position;
 
  while(back_position > 0 && array[back_position] < array[back_position-1])
  {
    temp = array[back_position];
    array[back_position] = array[back_position-1];
    array[back_position-1] = temp;
    back_position--;                 
  }
                                                                      
  }
 
  printf("\n Array after sorting:");
  for(i=0;i<array_size;i++)
  {
  printf("  %d\t",array[i]);
  }
  getche(); 
  return 0;
}

Analysis of insertion sort.

Best case - Already sorted data. Best efficiency in this case (o(n)). Just one pass through the data. No insertion happens.

Worst case - Data is sorted in reverse order. Efficiency in this case in (o(n^2)). Every pass of inner loop (while loop in our code above) will scan and shift the entire sorted part of the array and then insert the next element. The average case also has the efficiency of O(n^2).

Calculating worst case complexity -

To insert the last element from the unsorted array to a sorted array we need n-1 comparisons and n-1 shifts. Similarly to insert n-1 st element we need n-2 comparisons and n-2 shifts and so on.

Number of comparisons = n-1 + n-2 + .... + 1 = n(n-1)/2 = o(n^2)
Number of shifts = n-1 + n-2 + ...... + 1 = n(n-1)/2 = o(n^2)
So the complexity in worst case is of the order o(n^2).