Sorting Algorithm
In this tutorial we will learn about Insertion sort algorithm.
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.
a[1]
a[0]
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.
a[2]
In a similar way the process is carried out n-1 times.
/** * 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
#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; } }
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)