I need some help implementing the Radix sort algorthim in JavaScript.
I found this example online, with the following code, but I don't understand how I call the function since it appears to be tailored for that site:
// Radix sort a (base 2)
// Numbers must be in the range 0 to 2**31 - 1
function radixSort() {
readArray('i');
var b0 = new obj(); // Bin for 0 digits
var b1 = new obj(); // Bin for 1 digits
for (var i=0; i<32; ++i) {
if (form.step.checked) { // Single step
writeArray('i','a');
if (!confirm("Sort on bit "+i))
return;
}
var mask = 1<<i; // Digit (2**i)
var biggest = 2<<i; // If all of a is smaller, we're done
var zeros=0; // Number of elements in b0, b1
var ones=0;
var found=false; // Any digits past i?
for (var j=0; j<n; ++j) { // Sort into bins b0, b1
if ((a[j] & mask) == 0)
b0[zeros++] = a[j];
else
b1[ones++] = a[j];
if (a[j]>=biggest) // Any more digits to sort on?
found=true;
}
for (j=0; j<zeros; ++j) // Concatenate b0, b1 back to a
a[j]=b0[j];
for (j=0; j<ones; ++j)
a[j+zeros]=b1[j];
form.imoves.value = parseInt(form.imoves.value)+n;
if (!found)
break;
}
writeArray('i','a');
}
The term "radix sort" is a tricky one. There are actually two different sorts that work in a similar manner - MSB (most significant bit) radix and LSB (least significant bit) radix. (You will sometimes see the B replaced with a D for digit). Here are implementations of both.
MSB radix:
//arguments to sort an array:
//arr: array to be sorted
//begin: 0
//end: length of array
//bit: maximum number of bits required to represent numbers in arr
function sort(arr, begin, end, bit)
{
var i, j, mask;
i = begin;
j = end;
mask = 1 << bit;
while(i < j)
{
while(i < j && !(arr[i] & mask))
{
++i;
}
while(i < j && (arr[j - 1] & mask))
{
--j;
}
if(i < j)
{
j--;
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
}
}
if(bit && i > begin)
{
sort(arr, begin, i, bit - 1);
}
if(bit && i < end)
{
sort(arr, i, end, bit - 1);
}
}
sort(arr, 0, arr.length, 32); //Here I've assumed that the values in arr are integers that fit in 32 bits
LSB radix:
function insert(arr, i, j)
{
tmp = arr[i];
arr.splice(i, 1);
arr.splice(j, 0, tmp);
}
//arguments to sort an array:
//arr: array to be sorted
function sort(arr)
{
var bit, end, i, mask;
bit = 0;
while(true)
{
mask = 1 << bit;
i = 0;
end = arr.length;
while(i < end)
{
if(arr[i] & mask)
{
insert(arr, i, arr.length - 1);
end--;
}
else
{
i++;
}
}
bit++;
if(end === arr.length)
{
break;
}
}
}
I pulled these algorithms off of http://visualsort.appspot.com/. Then I compiled them to javascript at http://jashkenas.github.com/coffee-script/, and wrote the insert method/reformatted for readability.