Insertion Sort

This algorithm is very popular with bridge players when they sort their cards. In this procedure, we pick up a particular value and then insert it at the appropriate place in the sorted sub list.

This algorithm requires n-1 passes.

Pass1: a[1] is inserted either before or after a[0] so that a[0] and a[1] are sorted.
Pass2: a[2] is inserted either before a[0] or between a[0] and a[1] or after a[1] so that the elements a[0], a[1], a[2] are sorted.
Pass3: a[3] is inserted either before a[0] or between a[0] and a[1] or between a[1] and a[2] or after a[2] so that the elements a[0], a[1], a[2], a[3] are sorted.
Pass k: a[k] is inserted in its proper place in the sorted sub array a[0], a[1], a[2],…a[k-1] so that the elements a[0], a[1], a[2],…a[k-1],a[k] are sorted.
Pass n-1:a[n-1] is inserted in its proper place in the sorted sub array a[0], a[1], a[2],…a[n-2] so that the elements a[0], a[1], a[2],…a[n-1] are sorted.

Analysis of Insertion Sort

The worst-case performance occurs when the elements of the input array are in descending order.

In the worst-case, the first pass will require one comparison, the second pass will require 2 comparisons, and so on until the last pass which will require (n-1) comparisons. In general, the kth pass will require k-1 comparisons.

Therefore the total number of comparisons is:
F(n)=1+2+3+…..+(n-k)+….+(n-3)+(n-2)+(n-1)
=n(n-1)/2
=O(n²)

Algorithm

insertionsort(a,n)
Here a is a linear array with n elements. This algorithm sorts the elements in ascending order. It uses a temporary variable temp to facilitate the exchange of two values and variables j and k are used as loop control variables.

begin
for k=1 to (n-1) by 1 do
set temp=a[k]
set a[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

Complete Program

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

/**

 * Insertion sort

 * http://www.byteguide.com

 */

#include <stdio.h>

void insertionsort(int a[], int n)

{

    int i, k, y;

    for (k=1; k<n; k++)

    {

        y = a[k];

        for (i=k-1; i>=0 && y<a[i]; i--)

            a[i+1] = a[i];

        a[i+1] = y;

    }

}

int main()

{

    int a[50], n, i;

    printf("How many elements do you want to create the array with?"

        "max(50): ");

    scanf("%d", &n);

    fflush(stdout);

    puts("Enter the array elements");

    for (i=0; i<n; i++)

        scanf("%d", &a[i]);

    insertionsort(a, n);

    puts("--------Sorted Array--------");

    for (i=0; i<n; i++)

        printf("%d ", a[i]);

    printf("n");

    return 0;

}

Output

How many elements do you want to create the array with?(max 50): 6
Enter the array elements
3
67
85
89
56
44
——–Sorted Array——–
3
44
56
67
85
89