Implement Binary Insertion Sort using C++

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most and one must continuously keep sharpening these skills. And to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are specific approaches to solve problems in such a way that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, to keep things simple were going to start with some basic programs you must learn before moving on to complex algorithms. Therefore today we’re going to learn how to Implement Binary Insertion Sort using C++.

 

What is Binary Insertion Sort?

 

• Comes in the list of simplest data structures, Binary Insertion Sort is the advanced and efficient way of arranging elements in ascending order. The array is either sorted or is unsorted.

 

• The key thing separating Binary Insertion Sort from Insertion Sort is that to search for the swapping element we apply a binary search algorithm. Applying Binary Search reduces the time complexity.

 

• When the array is sorted this data structure works quickest. However, when elements aren’t sorted it works the slowest.

 

What’s The Approach?

 

• Consider arr[low..high] of size n we want to implement Binary Insertion Sort on. So firstly we’ll iterate a loop from 1 to n.

 

• Next, we’ll compare the element at iterating index with its preceding element from the array. If the comparing element is smaller, we’ll again compare it with the before elements.

 

•  We will use binary search to find the preceding element so, we’ll check if high <= low 

 

• if the above condition is true then we’ll return (item > a[low]) ? (low + 1) : low  . Here item is the element at the preceding index in the array. 

 

• Also, we’ll store the mid by performing mid = (low + high) / 2

 

• Next, we’ll also check whether item == a[mid] and if it is then we’ll return mid+1

 

• However if item > a[mid] is the case then we’ll return binarySearch(a, item,  mid + 1, high)

 

• Lastly, we’ll Move the greater elements one position up to make space for the swapped element.

 

Also Read: Print Prime Factors of A Number in C++

 

C++ Program To Implement Binary Insertion Sort

 

Input:

 

37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54

 

Output:

 

Sorted array: 

0 12 17 23 31 37 46 54 72 88 100

 

// C++ program for implementation of
// binary insertion sort
#include <iostream>
using namespace std;

// A binary search based function
// to find the position
// where item should be inserted
// in a[low..high]
int binarySearch(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 binarySearch(a, item,
                            mid + 1, high);
    return binarySearch(a, item, low,
                        mid - 1);
}

// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
    int i, loc, j, k, selected;

    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];

        // find location where selected should be inseretd
        loc = binarySearch(a, selected, 0, j);

        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}

// Driver Code
int main()
{
    int a[]
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int n = sizeof(a) / sizeof(a[0]), i;

    insertionSort(a, n);

    cout <<"Sorted array: \n";
    for (i = 0; i < n; i++)
        cout <<" "<< a[i];

    return 0;
}