binary_insertion_sort.cpp File Reference

Binary Insertion Sort Algorithm (Insertion Sort) More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for binary_insertion_sort.cpp:

Namespaces
namespace	sorting
	for working with vectors

Functions
template<class T >
int64_t	sorting::binary_search (std::vector< T > &arr, T val, int64_t low, int64_t high)
	Binary search function to find the most suitable pace for an element.
template<typename T >
void	sorting::insertionSort_binsrch (std::vector< T > &arr)
	Insertion sort function to sort the vector.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Binary Insertion Sort Algorithm (Insertion Sort)

If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2 n⌉ comparisons in the worst case. When each element in the array is searched for and inserted this is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series

• of swaps required for each insertion. However it has several advantages such as

1. Easy to implement
2. For small set of data it is quite efficient
3. More efficient that other Quadratic complexity algorithms like Selection sort or bubble sort.
4. It is efficient to use it when the cost of comparison is high.
5. It's stable that is it does not change the relative order of elements with equal keys.
6. It can sort the array or list as it receives.

Example execution steps:

1. Suppose initially we have

   \begin{bmatrix}40 &30 &20 &50 &10\end{bmatrix}

2. We start traversing from 40 till we reach 10 when we reach at 30 we find that it is not at it's correct place so we take 30 and place it at a correct position thus the array will become

   \begin{bmatrix}30 &40 &20 &50 &10\end{bmatrix}

3. In the next iteration we are at 20 we find that this is also misplaced so we place it at the correct sorted position thus the array in this iteration becomes

   \begin{bmatrix}20 &30 &40 &50 &10\end{bmatrix}

4. We do not do anything with 50 and move on to the next iteration and select 10 which is misplaced and place it at correct position. Thus, we have

   \begin{bmatrix}10 &20 &30 &40 &50\end{bmatrix}

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit.

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    /* descriptions of the following test */
    /* 1st test:
       [5, -3, -1, -2, 7] returns [-3, -2, -1, 5, 7] */
    std::vector<int64_t> arr1({5, -3, -1, -2, 7});
    std::cout << "1st test... ";
    sorting::insertionSort_binsrch(arr1);
    assert(std::is_sorted(std::begin(arr1), std::end(arr1)));
    std::cout << "passed" << std::endl;
 
    /* 2nd test:
       [12, 26, 15, 91, 32, 54, 41] returns [12, 15, 26, 32, 41, 54, 91] */
    std::vector<int64_t> arr2({12, 26, 15, 91, 32, 54, 41});
    std::cout << "2nd test... ";
    sorting::insertionSort_binsrch(arr2);
    assert(std::is_sorted(std::begin(arr2), std::end(arr2)));
    std::cout << "passed" << std::endl;
 
    /* 3rd test:
       [7.1, -2.5, -4.0, -2.1, 5.7] returns [-4.0, -2.5, -2.1, 5.7, 7.1] */
    std::vector<float> arr3({7.1, -2.5, -4.0, -2.1, 5.7});
    std::cout << "3rd test... ";
    sorting::insertionSort_binsrch(arr3);
    assert(std::is_sorted(std::begin(arr3), std::end(arr3)));
    std::cout << "passed" << std::endl;
 
    /* 4th test:
       [12.8, -3.7, -20.7, -7.1, 2.2] returns [-20.7, -7.1, -3.7, 2.2, 12.8] */
    std::vector<float> arr4({12.8, -3.7, -20.7, -7.1, 2.2});
    std::cout << "4th test... ";
    sorting::insertionSort_binsrch(arr4);
    assert(std::is_sorted(std::begin(arr4), std::end(arr4)));
    std::cout << "passed" << std::endl;
}

Here is the call graph for this function: