Binary Insertion Sort


Binary search is used to reduce the number of comparisons in Insertion sort. This modification is known as Binary Insertion Sort.

Binary Insertion Sort use binary search to find the proper location to insert the selected item at each iteration. In insertion sort, it takes O(i) (at ith iteration) in worst case. Using binary search, it is reduced to O(log i).

Complexity

  • Worst case time complexity: Θ(N log N) comparisons and swaps
  • Average case time complexity: Θ(N log N) comparisons and swaps
  • Best case time complexity: Θ(N) comparisons and Θ(1) swaps
  • Space complexity: Θ(1).

Implementation

Implementation of Binary Insertion Sort algorithm in 1 language that includes C.

  • C

C


 #include <stdio.h>
int binary_search(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 binary_search(a, item, mid+1, high);
    return binary_search(a, item, low, mid-1);
}
void insertion_sort(int a[], int n)
{
    int i, location = 0, j, k, selected, n = sizeof(a)/sizeof(a[0]);
    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i]; 
        location = binary_search(a, selected, 0, j);
        while (j >= location)
        {
            a[j+1] = a[j];
            --j;
        }
        a[j+1] = selected;
    }
}
int main()
{
    int a[] = {1,2,5,6,3,9,1};
    int i = 0;
    insertionSort(a);
    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ",a[i]);
    return 0;
}
Alexa Ryder

Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.

Read More