[AlgoExpert] Radix Sort

Radix Sort

  • Time : O(n log10(max element))
  • Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>
#include <queue>
using namespace std;

vector<int> radixSort(vector<int> array) {
if(array.empty()) return {};
int ma = log10(*max_element(begin(array), end(array))), p = 0, n = array.size();
for(int i = 0; i <= ma; i++) {
int d = pow(10, i);
queue<int> q[10];
for(int j = 0; j < n; j++) {
int bucket = (int)(array[j] / d) % 10;
q[bucket].push(array[j]);
}
for(int j = 0, idx = 0; j < 10; j++) {
while(!q[j].empty()) {
array[idx++] = q[j].front();
q[j].pop();
}
}
}
return array;
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/10/PS/AlgoExpert/radix-sort/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.