Skip to content

Instantly share code, notes, and snippets.

@attractivechaos
Created June 7, 2012 04:58
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save attractivechaos/2886685 to your computer and use it in GitHub Desktop.
Save attractivechaos/2886685 to your computer and use it in GitHub Desktop.
Fast radix sort
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#define rstype_t uint64_t // type of the array
#define rskey(x) (x) // specify how to get the integer from rstype_t
#define RS_MIN_SIZE 64 // for an array smaller than this, use insertion sort
typedef struct {
rstype_t *b, *e; // begin and end of each bucket
} rsbucket_t;
void rs_insertsort(rstype_t *beg, rstype_t *end) // insertion sort
{
rstype_t *i;
for (i = beg + 1; i < end; ++i)
if (rskey(*i) < rskey(*(i - 1))) {
rstype_t *j, tmp = *i;
for (j = i; j > beg && rskey(tmp) < rskey(*(j-1)); --j)
*j = *(j - 1);
*j = tmp;
}
}
// sort between [$beg, $end); take radix from ">>$s&((1<<$n_bits)-1)"
void rs_sort(rstype_t *beg, rstype_t *end, int n_bits, int s)
{
rstype_t *i;
int size = 1<<n_bits, m = size - 1;
rsbucket_t *k, b[size], *be = b + size; // b[] keeps all the buckets
for (k = b; k != be; ++k) k->b = k->e = beg;
for (i = beg; i != end; ++i) ++b[rskey(*i)>>s&m].e; // count radix
for (k = b + 1; k != be; ++k) // set start and end of each bucket
k->e += (k-1)->e - beg, k->b = (k-1)->e;
for (k = b; k != be;) { // in-place classification based on radix
if (k->b != k->e) { // the bucket is not full
rsbucket_t *l;
if ((l = b + (rskey(*k->b)>>s&m)) != k) { // different bucket
rstype_t tmp = *k->b, swap;
do { // swap until we find an element in bucket $k
swap = tmp; tmp = *l->b; *l->b++ = swap;
l = b + (rskey(tmp)>>s&m);
} while (l != k);
*k->b++ = tmp; // push the found element to $k
} else ++k->b; // move to the next element in the bucket
} else ++k; // move to the next bucket
}
for (b->b = beg, k = b + 1; k != be; ++k) k->b = (k-1)->e; // reset k->b
if (s) { // if $s is non-zero, we need to sort buckets
s = s > n_bits? s - n_bits : 0;
for (k = b; k != be; ++k)
if (k->e - k->b > RS_MIN_SIZE) rs_sort(k->b, k->e, n_bits, s);
else if (k->e - k->b > 1) rs_insertsort(k->b, k->e);
}
}
void radix_sort(rstype_t *beg, rstype_t *end)
{
if (end - beg <= RS_MIN_SIZE) rs_insertsort(beg, end);
else rs_sort(beg, end, 8, sizeof(rskey(*beg)) * 8 - 8);
}
int main(int argc, char *argv[])
{
size_t i, n = 10;
uint64_t *a;
if (argc > 1) n = atoi(argv[1]);
a = malloc(8 * n);
for (i = 0; i < n; ++i) a[i] = lrand48()&0xff;
fprintf(stderr, "["); for (i = 0; i != n; ++i) { if (i) fprintf(stderr, ", "); fprintf(stderr, "%lld", a[i]); } fprintf(stderr, "]\n");
radix_sort(a, a + n);
fprintf(stderr, "["); for (i = 0; i != n; ++i) { if (i) fprintf(stderr, ", "); fprintf(stderr, "%lld", a[i]); } fprintf(stderr, "]\n");
free(a);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment