Insertion Sort

An insertion sort is one that sorts a set of values by inserting values into existing sorting files. Suppose an array a with n element a[i],a[2]....a[n]is in memory. The insertion sort algorithm scans a from a[1] to a[n] inserting each element a[k] into its proper position in the previously sorted subarray a[1],a[2]......a[k-1]

pass1:
a[1] by itself is trivially sorted.

pass2:
a[2] is inserted either before or after a[1] so that a[1],a[2] is sorted

pass3:

a[3] is inserted into its proper place in a[1],a[2] that is before a[1] between a[1] and a[2] or after a[2] so that a[1],a[2],a[3] is sorted.

pass4:

a[4] is inserted into proper place in a[1],a[2]so that a[1]],a[2],a[3],a[4] is sorted.

pass n:

a[n] is inserted into its proper place in a[1],a[2],a[3]...a[n-1] so that a[1],a[2]...a[n] is sorted.

Algorithm:

1. Set K = 1.
2. For K=1 to (n-1)
3. Set temp = a[K]
4. Set j =K-1
5. While temp < a[j] and (j >=0) perform the following steps.
6. Set a[j + 1] = a[j]
7. End of loop.
8. Assign the value of temp to a[j + 1]
9. End of for loop.
10. 3.Exit.

Example:

Step 1: Assume 54 is a sorted list of 1 item

54 26 93 17 77 31 44 55 20

Step 2: Inserted 26

26 54 93 17 77 31 44 55 20

Step 3: Inserted 93

26 54 93 17 77 31 44 55 20

Step 4: Inserted 17

17 26 54 93 77 31 44 55 20

Step 5: Inserted 77

17 26 54 77 93 31 44 55 20

Step 6: Inserted 31

17 26 31 54 77 93 44 55 20

Step 7: Inserted 44

17 26 31 44 54 77 93 55 20

Step 8: Inserted 55

17 26 31 44 54 55 77 93 20

Step 9: Inserted 20

17 20 26 31 44 54 55 77 93

Listing: Following program is showing the implementation of Insertion sort.

/* 
* C Program to Implement Insertion Sort 
*/ 
#include <stdio.h> 
#define MAX 7 

void insertion_sort(int *); 

void main() 
{ 
    int a[MAX], i; 

    printf("enter elements to be sorted:"); 
    for (i = 0;i < MAX;i++) 
    { 
        scanf("%d", &a[i]); 
    } 
    insertion_sort(a); 
    printf("sorted elements:\n"); 
    for (i = 0;i < MAX; i++) 
    { 
        printf(" %d", a[i]); 
    } 
} 

/* sorts the input */ 
void insertion_sort(int * x) 
{ 
    int temp, i, j; 

    for (i = 1;i < MAX;i++) 
    { 
        temp = x[i]; 
        j = i - 1; 
        while (temp < x[j] && j >= 0) 
        { 
            x[j + 1] = x[j]; 
            j = j - 1; 
        } 
        x[j + 1] = temp; 
    } 
} 

Output: 
    /* Average case */ 
    
    enter elements to be sorted:8 2 4 9 3 6 1 
    sorted elements: 
     1 2 3 4 6 8 9 
     
    /* Best case */ 
    
    enter elements to be sorted:1 2 3 4 5 6 7 
    sorted elements: 
     1 2 3 4 5 6 7 
     
    /* Worst case */ 
    
    enter elements to be sorted:7 6 5 4 3 2 1 
    sorted elements: 
     1 2 3 4 5 6 7