• Insertion Sort

    Insertion Sort

    Introduction:

    In insertion sort the element is inserted at an appropriate place similar to card insertion. Here the list is divided into two virtual parts called unsorted and sorted. In each pass, the first element of unsorted sub list is picked up and moved into the sorted sub list by inserting it in suitable position. Suppose, we have “n” elements, we need n-1 passes to sort the elements.

    Insertion sort works the way we might sort a hand of playing cards:

    1. We start with an empty hand [sorted array] and the cards face down on the table [unsorted array].
    2. Then collect one card[key] at a time from the table [unsorted array], and insert it into the correct position in the left hand [sorted array].
    3. To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.

    Algorithm of Insertion Sort:

    Insertion_sort (l,n)Where l -> Represents the list of elements.

    N -> Represents number of elements in the list.

    Step 1: [Initialize]

    1[0] = -0

    Step 2: Repeat through Step 3 to 5 for i=1,2,3,4..n

    Step 3: (i) temp = l[i]

    (ii) pointer = i – 1

    Step 4: while(temp < l[pointer])

    (i)                   l[pointer + 1] = l[pointer]

    (ii)                 pointer = pointer – 1

    Step 5: l[pointer] = temp

    Step 6: Exit

    Example of Insertion Sort on Array/List using C Language

    #Include<stdio.h>#include<stdlib.h>

    int i, k;

    void insertion_sort (int *, int);

    void display(int *,int)

    void insertion_sort(int l[], int n)

    {

    int pointer, temp;

    l[0] = -0;

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

    {

    pointer = i –1;

    temp = l[i];

    while(temp <l[ponter])

    {

    l[pointer+1] = l[pointer];

    pointer -;

    }

    l[pointer+1] = temp;

    printf(“Step = %d”,i);

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

    printf(“%d”, l[k]);

    printf(“\n”);

    }

    }

    void display(int l[], int n)

    {

    printf(“\n Sorted list is as follows\n”);

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

    printf(“%d”,l[i]);

    }

    void main()

    {

    int nember = 20;

    int list[100];

    int i;

    printf(“\n Number of elements in the list : %i” , number);

    printf(“\n Unsorted list is as follows \n”);

    for(i = 1;i <= number; i++)

    {

    list[i] = rand() %100;

    printf(“%d”,list[i]);

    }

    printf(“\n”);

    printf(“\n Stepwise result is as follows \n\n”);

    insertion_sort(list, number);

    display(list, number);

    }

    Appreciate my work :Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInPin on PinterestShare on RedditShare on StumbleUponShare on TumblrDigg thisShare on YummlyShare on VKFlattr the authorBuffer this page

Leave a Reply

Your email address will not be published. Required fields are marked *