In this tutorial we shall go through the concept of insertion sort and how to implement in C language.
Steps to do insertion sort is explained below:
1. We need to take 2 loops.
2. Outer Loop will loop through all the elements in the array list. Here we consider first element as the smallest element.
3. Inner loop is used to check for that if there is any smallest element present, than the element we considered in the outer loop.
4. If present, then we shall swap the element to the index of the outer loop.
Here in the first pass, the smallest element will be in the first position. Second pass, second smallest element will be in the 2nd position and so on.
Let us understand insertion sort with an example:
Consider the array, [5, 4, 1, 2, 3].
Implementation of Insertion Sort using C
#include <stdio.h> #include <math.h> void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i-1; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } int main() { int n,i,arr[100]; printf("Enter the size of the array: "); scanf("%d",&n); printf("Enter the elements of the array:"); for(i=0; i<n; i++) { scanf("%d",&arr[i]); } insertionSort(arr, n); printf("After sorting:"); for(i=0; i<n; i++) { printf("%d ",arr[i]); } return 0; }
Output:
Enter the length of the array 5 Enter the array elements of length 5 5 4 3 2 1 The sorted array is 1 2 3 4 5
Running time at worst case for Insertion sort:
As we are using 2 for loops, the worst case complexity is O(n^2).
Further Reading:
Deepak Rajpurohit
python code for insertion sort-:
def insertion(arr):
for i in range(1,len(arr)):
key = arr[i]
j=i-1
while j>=0 && arr[j]>key:
arr[j+1] = arr[j]
j-=1
arr[j+1] = key
# DRIVER CODE
arr = [19,7,2,5,6]
insertion(arr)
for i in range(len(arr)):
print(arr[i])