Insertion sort, This algorithm repeatedly adds new element to the sorted result. In this algorithm we take first element as the sorted sub-array. Then we take second element and puts it into the first sorted sub-array at its correct position (i.e we do shifting if necessary). Then we take third element and put it into first sorted sub-array and repeat the same till all the elements are inserted into the sorted sub-array. Personally saying, I like this algorithm more than quicksort especially if less number of elements are in unsorted manner or if I have to insert an additional element during sorting the process because this algorithm can simply put that new element at its correct position rather than sorting the whole array again. This algorithm take maximum time when all the elements of array are in reverse order.

Algorithm:

**Time Complexity:**O(n^2)Algorithm:

**Algorithm:**

step 1: do for i=1 to n

step 2: set: key=arr[i]

step 3: set: j=i-1

step 4: doWhile arr[j]>key and j>=0:

step 5: set: arr[j+1]=arr[j]

step 6: set: j=j-1

step 7: EndWhile

step 8: set: arr[j+1]=key

step 2: set: key=arr[i]

step 3: set: j=i-1

step 4: doWhile arr[j]>key and j>=0:

step 5: set: arr[j+1]=arr[j]

step 6: set: j=j-1

step 7: EndWhile

step 8: set: arr[j+1]=key

**Example:**

Let a[] = { 24, 12, 4, 9, 6 }

Pass 1, i=1: { 12, 24, 4, 9, 6}

Pass 2, i=2: { 4, 12, 24, 9, 6}

Pass 3, i=3: { 4, 9, 12, 24, 6}

Pass 4, i=4: { 4, 6, 9, 12, 24}

C Program for Implementation of Insertion Sort

#include <stdio.h> #define MAX 100 void insertion_sort(int arr[],int n); int main() { int n,arr[MAX]; int i; printf("\nEnter the total number of elements: "); scanf("%d",&n); printf("\nEnter the elements of array: \n"); for(i=0;i<n;i++) { scanf("%d",&arr[i]); } printf("\nOriginaly array:\n"); for(i=0;i<n;i++) { printf("%d ",arr[i]); } printf("\n\n"); insertion_sort(arr,n); printf("\n\nArray after sorting: \n"); for(i=0;i<n;i++) { printf("%d ",arr[i]); } return 0; } void insertion_sort(int arr[],int n) { int i,key,j,k; for(i=1;i<n;i++) { key=arr[i]; j=i-1; while(arr[j]>key && j>=0) { arr[j+1]=arr[j]; j=j-1; } arr[j+1]=key; printf("\nPass %d: ",i); for(k=0;k<n;k++) { printf("%d ",arr[k]); } } }

**OUTPUT:**

**See also: Implementation of Selection Sort in C**

EmoticonEmoticon