Insertion Sort

In this tutorial we will learn about Insertion sort algorithm.

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, element 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

#include 

//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(n²)