Insertion Sort

Sorting Algorithm

Share

About Insertion Sort

In this technique we pick an element and then insert it at the appropriate position in ascending or descending order.
In pass 1, element a[1] is inserted either before or after a[0] so that a[0] and a[1] are sorted.
In pass 2, a[2] is inserted either before a[0] or between a[0] and a[1] or after a[1] so that a[0], a[1] and a[2] are sorted.
In a similar way the process is carried out n-1 times.

  • Insertion sort requires n – 1 pass to sort an array of n elements.
  • In each pass we insert the current element at the appropriate place so that the elements in the current range is in order.
  • In each pass we have k comparisons, where k is the pass number.
    So, 1st pass requires 1 comparison,
    kth pass requires k – 1 comparisons and
    the last pass requires n – 1 comparisons

Algorithm


/*
a[0:n-1] is an array of n elements.
temp is a variable to facilitate exchange.
*/
InsertionSort(a,n)
Begin
    for k = 1 to n-1 by 1 do	//this is for pass
        Set temp = a[k];
        Set j = k-1;
        while( temp < a[j] and j >= 0) do
            Set a[j+1] = a[j];
            Set j = j-1;
        endwhile
        Set a[j+1] = temp;
    endfor
End

Code in C


Code in C


#include <stdio.h>

//function declaration
void insertionSort(int *a, int n);

int main(){
	//variable declaration
	int arr[5], i;
	
	//input
	for(i = 0; i < 5; i++)
		scanf("%d", &arr[i]);
	
	//sort
	insertionSort(arr, 5);	//passing arr address and no. of elements
	
	//output
	for(i = 0; i < 5; i++)
		printf("%d\n", arr[i]);
		
	return 0;
}

//function definition
void insertionSort(int *a, int n){
	int k, j, temp;
	for(k = 1; k <= n-1; k++){
		temp = a[k];
		j = k-1;
		while(temp < a[j] && j >= 0){
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = temp;
	}
}

Time Complexity

1st pass requires 1 comparison
2nd pass required 2 comparison
... last pass requires (n-1) comparison
So, total comparison = 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n2)

Share