Insertion sort program in C. Given an unsorted array, write a c program to sort an array using insertion sort.
In this tutorial, we are going to discuss following points.
i) What is insertion sort.
ii) How it’s different from Selection sort and Bubble sort.
iii) Insertion sort algorithm and it’s implementation using C program.
I have already discussed following sorting algorithms in my previous tutorials.
What is Insertion Sort?
Insertion sort is a simple sorting algorithm that takes one element in each iteration and put it at correct location. At each iteration it insert the element at its correct location and this process is repeated until complete array is sorted.
Insertion Sort –
i) Does not change the relative order of elements with equal keys.
ii) Requires constant memory O(1).
The time complexity of insertion sort is O(n^2).
Best Case : O(n)
Average Case : O(n2)
Worst Case : O(n2)
How Insertion Sort Works?
For example – Let’s take an array with following elements.
{6, 5, 3, 1, 8, 4}
Insertion Sort Explained
Step 1– 5 is compared with 6 and position is swapped.
After step 1 – {5, 6, 3, 1, 8, 4}
Step 2 – In next step 3 is compared with 6 and 5 and position is swapped.
After step 2 – {3, 5, 6, 1, 8, 4}
Step 3 – After that, 1 is placed at correct position.
After step 3 – {1, 3, 5, 6, 8, 4}
Step 4– 8 is compared with 6 , 5 , 3, 1 . 8 is at correct position no need to swap.
After step 4 – {1, 3, 5, 6, 8, 4}
Step 5 – After step 5, element 4 is paced at correct location.
After step 5 – {1, 3, 4, 5, 6, 8}
Now, All the elements of an array is sorted.
Insertion Sort Algorithm
We have discussed how insertion sort works now let’s see it’s Pseudocode.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
/* Iterate from 1 to arrlen -1 . */ for i = 1 to length(A) - 1 x = A[i] j = i-1 /* Put element at it's correct position. */ while j > 0 and A[j] > x A[j+1] = A[j] j = j - 1 A[j+1] = x |
Insertion Sort Program in C
We have discussed how insertion sort works and it’s algorithm. Let’s write a c program to implement insertion sort algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
//Insertion Sort Program in C #include <stdio.h> int main() { int arr[100],n,i,j,temp; printf("Enter number of elements \n"); scanf("%d",&n); printf("Enter the values \n"); for(i=0; i<n; i++) { scanf("%d",&arr[i]); } /* Insertion sort logic. */ for(i=1; i<n; i++) { temp = arr[i]; j = i - 1; while(j>=0 && temp<arr[j]) { arr[j+1] = arr[j]; --j; } arr[j+1]= temp; } /* After sorting. */ for (i=0; i<n; i++){ printf("%d ",arr[i]); } return 0; } |
When to use Insertion Sort ?
Insertion sort is good for small data sets. For large data sets use more efficient sorting algorithm such as QuickSort, HeapSort and MergeSort.
