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:

Go to the source code of this file.

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}

Definition in file binary_insertion_sort.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit.

Definition at line 143 of file binary_insertion_sort.cpp.

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

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 104 of file binary_insertion_sort.cpp.

                   {
    /* 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;
}