Binary insertion sort

Binary insertion sort

Binary insertion sort use binary search procedure to find the proper location to insert the selected item at each iteration. It reduces number of comparisons in normal insertion sort. This procedure reduces to O(log i) time each iteration of sort procedure.

Program:

#include<stdio.h>

#include<conio.h>

void sort(int [ ], int);

void bsearch(int [ ], int, int, int);

void main()

{

    int a[6] = {37, 23, 0, 17, 12, 72}, i;

    clrscr();

    sort(a , 6);

    printf("Sorted array: \n");

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

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

}

int bsearch(int a[ ], int item, int low, int high)

{

    if (high <= low)

    {

        return (item > a[low])?  (low + 1): low;

    }   

     int mid = (low + high)/2;

     if(item == a[mid])

     {

         return mid+1;

     }    

    if(item > a[mid])

    return bsearch(a, item, mid+1, high);

     else

    return bsearch(a, item, low, mid-1);

}

void sort(int a[ ], int n)

{

    int i, loc, j, selected;

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

    {

         j = i - 1;

         selected = a[i];

         loc = bsearch(a, selected, 0, j);

         while (j >= loc)

        {

            a[ j+1] = a[ j ];

            j--;

         }

        a[ j+1] = selected;

    }

}

Share on Google Plus