## C++, sort, pigeonhole_sort.cpp

``````/**
* @file
* @brief Implementation of [Pigeonhole Sort algorithm]
* (https://en.wikipedia.org/wiki/Pigeonhole_sort)
* @author [Lownish](https://github.com/Lownish)
* @details
* 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 \f\$O(n+N)\f\$.
*/

#include <algorithm>  //for std::is_sorted
#include <array>      //for std::array
#include <cassert>    //for assert
#include <iostream>   //for io operations

/**
* @namespace sorting
* @brief Sorting algorithms
*/
namespace sorting {

/**
* Pigeonhole sorting of array of size n
* The function will sort the array through Pigeonhole algorithm and print
* @param arr unsorted array of elements
* @returns sorted array of elements
*/
template <std::size_t N>
std::array<int, N> pigeonSort(std::array<int, N> arr) {
// Finding min and max*
auto min = std::min_element(std::begin(arr), std::end(arr));
auto max = std::max_element(std::begin(arr), std::end(arr));

// Range refers to the number of holes required
int range = *max - *min + 1;
int *hole = new int[range]();

// Copying all array values to pigeonhole
for (int i = 0; i < N; i++) {
hole[arr[i] - *min] = arr[i];
}

// Deleting elements from list and storing to original array
int count = 0;
for (int i = 0; i < range; i++) {
while (hole[i] != '\0') {
arr[count] = hole[i];
hole[i] = {};
count++;
}
}
delete[] hole;

return arr;
}
}  // namespace sorting

/**
* Test function 1 with unsorted array
* {8, 3, 2, 7, 4, 6, 8}
* @returns none
*/
static void test_1() {
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 function 2 with unsorted array
* {802, 630, 20, 745, 52, 300, 612, 932, 78, 187}
* @returns none
*/
static void test_2() {
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 function 1 with unsorted array
* {11,13,12,14}
* @returns none
*/
static void test_3() {
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";
}

/**
* Main function
*/
int main() {
test_1();
test_2();
test_3();

return 0;
}
``````