forked from ddhira123/Algorithms-HacktoberFest
-
Notifications
You must be signed in to change notification settings - Fork 0
/
CountingSort.cpp
67 lines (55 loc) · 1.49 KB
/
CountingSort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <vector>
#include <limits>
#include <type_traits>
#include <algorithm>
#include <iostream>
using std::vector;
template<typename T>
void countingSort(vector<T>& unsorted, const T minValue, const T maxValue)
{
// define count space
const T COUNT_SPACE_SIZE = maxValue - minValue + 1;
std::vector<T> countSpace(COUNT_SPACE_SIZE, 0);
// count number of T occurances using T as an index
for (T& i : unsorted)
countSpace[i - minValue]++;
// sort by looking at all non zero counts and transfering
// their index to unsorted array
size_t j = 0;
for (T i = 0; i < COUNT_SPACE_SIZE && j < unsorted.size(); ++i)
{
while (countSpace[i]-- > 0)
unsorted[j++] = i + minValue;
}
}
template<typename T>
void countingSort(vector<T>& unsorted)
{
static_assert(std::is_integral<T>::value, "Counting sort only works with integer values.");
// find the max and min values in the unsorted array to calculate count space size
T minValue = std::numeric_limits<T>::max(), maxValue = std::numeric_limits<T>::min();
for (const T n : unsorted)
{
minValue = std::min(minValue, n);
maxValue = std::max(maxValue, n);
}
// sort
countingSort(unsorted, minValue, maxValue);
}
template<typename T>
void print(const vector<T>& nums)
{
for (auto c : nums)
std::cout << c << " ";
std::cout << "\n";
}
int main(int argc, char** argv)
{
vector<int> numbers {-4, 2, 2, 4, 1, 6, 9, 100};
std::cout << "Unsorted: ";
print(numbers);
countingSort(numbers);
std::cout << "Sorted: ";
print(numbers);
return 0;
}