blob: be662f2bb63c11dde00e75dd8d375eddf682433d (
plain) (
blame)
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
|
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
void countingSort(std::vector<unsigned>& v) {
unsigned elementRange = *std::max_element(v.begin(), v.end()) + 1;
std::vector<unsigned> count(elementRange, 0);
std::vector<unsigned> result(v.size());
for (size_t i = 0; i < v.size(); i++)
count[v[i]]++;
for (size_t i = 1; i < elementRange; i++)
count[i] += count[i - 1];
for (int i = v.size() - 1; i >= 0; i--) {
result[count[v[i]] - 1] = v[i];
count[v[i]]--;
}
v = std::move(result);
}
int main() {
std::vector<unsigned> v;
const int length = 10000;
for (size_t i = 0; i < length; i++)
v.push_back(rand() * rand());
countingSort(v);
assert(std::is_sorted(v.begin(), v.end()));
// for (int x : v) {
// std::cout << x << " ";
// }
}
|