Search code examples
javascriptalgorithmsortingradix

Assist with implementing Radix Sort in JavaScript


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');
}

Solution

  • 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.