pigeonhole_sort.cpp File Reference

Implementation of [Pigeonhole Sort algorithm] (https://en.wikipedia.org/wiki/Pigeonhole_sort) More...

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>

Include dependency graph for pigeonhole_sort.cpp:

Go to the source code of this file.

Namespaces
namespace	sorting
	for working with vectors

Functions
template<std::size_t N>
std::array< int, N >	sorting::pigeonSort (std::array< int, N > arr)
static void	test_1 ()
static void	test_2 ()
static void	test_3 ()
int	main ()

Detailed Description

Implementation of [Pigeonhole Sort algorithm] (https://en.wikipedia.org/wiki/Pigeonhole_sort)

Author

Lownish

Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same. It requires O(n + Range) time where n is number of elements in input array and ‘Range’ is number of possible values in array.

The time Complexity of the algorithm is \(O(n+N)\).

Definition in file pigeonhole_sort.cpp.

Function Documentation

main()

int main

(

void

)

Main function

Definition at line 127 of file pigeonhole_sort.cpp.

           {
    test_1();
    test_2();
    test_3();
 
    return 0;
}

test_1()

static void test_1 ( )

static

Test function 1 with unsorted array {8, 3, 2, 7, 4, 6, 8}

Returns

none

Definition at line 68 of file pigeonhole_sort.cpp.

                     {
    const int n = 7;
    std::array<int, n> test_array = {8, 3, 2, 7, 4, 6, 8};
 
    test_array = sorting::pigeonSort<n>(test_array);
 
    assert(std::is_sorted(std::begin(test_array), std::end(test_array)));
 
    // Printing sorted array
    for (int i = 0; i < n; i++) {
        std::cout << test_array.at(i) << " ";
    }
    std::cout << "\nPassed\n";
}

test_2()

static void test_2 ( )

static

Test function 2 with unsorted array {802, 630, 20, 745, 52, 300, 612, 932, 78, 187}

Returns

none

Definition at line 88 of file pigeonhole_sort.cpp.

                     {
    const int n = 10;
    std::array<int, n> test_array = {802, 630, 20,  745, 52,
                                     300, 612, 932, 78,  187};
 
    test_array = sorting::pigeonSort<n>(test_array);
 
    assert(std::is_sorted(std::begin(test_array), std::end(test_array)));
 
    // Printing sorted array
    for (int i = 0; i < n; i++) {
        std::cout << test_array.at(i) << " ";
    }
    std::cout << "\nPassed\n";
}

test_3()

static void test_3 ( )

static

Test function 1 with unsorted array {11,13,12,14}

Returns

none

Definition at line 109 of file pigeonhole_sort.cpp.

                     {
    const int n = 4;
    std::array<int, n> test_array = {11, 13, 12, 14};
 
    test_array = sorting::pigeonSort<n>(test_array);
 
    assert(std::is_sorted(std::begin(test_array), std::end(test_array)));
 
    // Printing sorted array
    for (int i = 0; i < n; i++) {
        std::cout << test_array.at(i) << " ";
    }
    std::cout << "\nPassed\n";
}