ruby_radix

ruby_radix.c

// --------------------------------------------------------------------
// Radix Sort for Ruby
// josh@bcg.io
// 
// EXAMPLE:
// --------------------------------------------------------------------
// require 'ruby_radix'
// [10,2,24,38,1,9,42].radix_sort
// => [1, 2, 9, 10, 24, 38, 42]
//
// BENCHMARKS:
// --------------------------------------------------------------------
// 1,000,000 values (1 pass)
//                            user     system      total        real
// ruby sort:             0.230000   0.000000   0.230000 (  0.231326)
// dphase radix sort:     0.160000   0.000000   0.160000 (  0.155739)
//
// 1,000,000 values (500 passes)
//                            user     system      total        real
// ruby sort:           117.290000   0.720000 118.010000 (118.023315)
// dphase radix sort:    76.520000   0.180000  76.700000 ( 76.699993)
// --------------------------------------------------------------------
//
// ISSUES:
// --------------------------------------------------------------------
// - Doesn't sort negative integers
// - Fails test with 10 million elements, not sure where this begins
// --------------------------------------------------------------------

#include "ruby.h"

void 
radix_sort(VALUE *array, signed long int elements) {
  signed long int i, b[elements], m = array[0], exp = 1;

  for (i = 0; i < elements; i++) {
    if ((signed)array[i] > m) m = array[i];
  }

  while (m / exp > 0) {
    int bucket[10] = {0};
    for (i = 0; i < elements; i++)      bucket[array[i] / exp % 10]++;
    for (i = 1; i < 10; i++)            bucket[i] += bucket[i - 1];
    for (i = elements - 1; i >= 0; i--) b[--bucket[array[i] / exp % 10]] = array[i];
    for (i = 0; i < elements; i++)      array[i] = b[i];
    exp *= 10;
  }
}

VALUE 
ruby_radix(VALUE self) {
  radix_sort(RARRAY_PTR(self), RARRAY_LEN(self));
  return self;
}

void 
Init_ruby_radix() {
  rb_define_method(rb_cArray, "radix_sort", ruby_radix, 0);
}