Skip to content

Instantly share code, notes, and snippets.

@kaja47
Last active May 27, 2017 14:08
Show Gist options
  • Save kaja47/40b7b441f3552c8396bb8d49f34cb95b to your computer and use it in GitHub Desktop.
Save kaja47/40b7b441f3552c8396bb8d49f34cb95b to your computer and use it in GitHub Desktop.
radix sort in D
T[] radixsort(T)(T[] arr, T[] tmparr) {
assert(arr.length == tmparr.length);
int[256][T.sizeof] counts;
foreach (v; arr) {
foreach (b; 0 .. T.sizeof) {
uint c = (v >> (b * 8)) & 0xff;
counts[b][c] += 1;
}
}
loop: foreach (b; 0 .. T.sizeof) {
int zeroCounts = 0;
foreach (c; counts[b]) {
if (c == 0) zeroCounts++;
}
if (zeroCounts == 255) continue loop;
int[256] offsets;
foreach (i; 1..256) {
offsets[i] = counts[b][i-1] + offsets[i-1];
}
foreach(v; arr) {
uint c = (v >> (b * 8)) & 0xff;
tmparr.ptr[offsets[c]] = v;
offsets[c] += 1;
}
auto tmp = arr;
arr = tmparr;
tmparr = tmp;
}
return arr;
}
void main() {
import std.datetime;
import std.conv;
import std.random;
import std.range;
import std.stdio;
import std.algorithm.sorting;
import std.algorithm.iteration;
alias T = uint;
int len = 16*1024*1024;
auto rnd = Random(47);
T[] src = array(rnd.take(len).map!(a => to!T(((to!ulong(a)<<32)+a) & (T.max)) ));
T[] arr = new T[len];
T[] tmp = new T[len];
foreach (iter; 0..4) {
arr[] = src[];
StopWatch sw;
sw.start();
auto sorted = radixsort(arr, tmp);
sw.stop();
writeln(isSorted(sorted));
writeln(sw.peek().usecs / 1000.0, " ms");
writeln("* ", sw.peek().hnsecs * 1.0 * 100 / len, " ns/el");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment