forked from fineanmol/Hacktoberfest2024
-
Notifications
You must be signed in to change notification settings - Fork 0
/
counting.cpp
42 lines (40 loc) · 793 Bytes
/
counting.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
#include <bits/stdc++.h>
using namespace std;
#define RANGE 255
#define ll long long int
vector<ll> countSort(vector<ll> arr)
{
ll max = INT_MIN;
for (auto i : arr)
{
if (i > max)
max = i;
}
vector<ll> F(max + 1, 0);
for (auto i : arr)
F[i]++;
// Commulative
for (int i = 1; i <= arr.size(); i++)
{
F[i] = F[i] + F[i - 1];
}
vector<ll> ans(arr.size(), 0);
for (int i = 0; i < arr.size(); i++)
{
F[arr[i]]--;
ans[F[arr[i]]] = arr[i];
}
return ans;
}
int main()
{
ll n;
cin >> n;
vector<ll> V(n);
for (auto &i : V)
cin >> i;
V = countSort(V);
cout << endl;
for (auto i : V)
cout << i << " ";
}