Implementing RadixSort using JavaScript

Question

Can someone review my code? I am trying to implement radix sort in JavaScript.

var numbers = [90, 46, 7, 12, 100, 68];
var length = numbers.length;
var buckets = new Array(10);

Clear();
function Clear() {
    for (var i = 0; i < 10; i++)
        buckets[i] = [];
}

RadixSort();
function RadixSort() {
    var maxElement = Math.max.apply(null , numbers);
    var maxDigits = GetDigitsCount(maxElement);
    var count = 0;
    while (count < maxDigits) {
        CopyToArray();
        for (var index = 0; index < length; index++) {
            var tenIndex = Math.pow(10, count);
            var remNumber = parseInt(numbers[index] / tenIndex, 10);
            var bucketIndex = remNumber % 10;
            buckets[bucketIndex].push(numbers[index]);
        }
        count++;
    }
    for (var i = 0; i < 9; i++) {
        var arr = buckets[i];
        var arrLength = arr.length;
        for (var j = 0; j < arrLength; j++)
            console.log(arr[j]);
    }
}

function GetDigitsCount(number) {
    var count = 0;
    while (number > 0) {
        number = parseInt(number / 10);
        count++;
    }
    return count;
}

function CopyToArray() {
    var k = 0;
    for (var i = 0; i < 10; i++) {
        var arr = buckets[i];
        var arrLength = arr.length;
        for (var j = 0; j < arrLength; j++) {
            numbers[k++] = arr[j];
        }
        buckets[i] = [];
    }
}

Answer 1

Your code is not finished.

I could not say this is a finished bit of code as it simply does not work. A simple test, a random set of integers and comparing it to the result of the standard sort showed that more often than not the function just failed.

Read this Gramma and types

---

3 rules of coding:

1. There is no code without testing.
2. There is no code without testing.
3. There is no code without testing.

When creating a function such as this it is important that you have a reliable means of testing the code over all possible inputs. One test case just does not cut it. Having a full test at the start makes writing the code a lot easier. You can make a change and instantly test all possible inputs, it also helps you optimise the code once you have the basics worked out.

Example test function

This is the function that I used to test your code. It creates a random list of numbers of different lengths, different numbers of digits, and different ranges of digits. If it fails any test then it stops displaying the failed array and the correct array.

function test() {
    function log (data) {console.log(data); }
    function createRandomArray (maxItems, maxDigits, digitRange) {
        var numSize, num;
        var numbers = [];
        var count = Math.random() * maxItems;
        while (count-- > 0) {
            numSize = Math.random() * maxDigits;
            num = 0;
            while (numSize-- > 0) {
                num *= 10;
                num += Math.floor(Math.random() * digitRange);
            }
            numbers.push(num);
        }
        return numbers;
    }
    var items, digits, range, array;
    for (items = 0; items <= 20; items += 1) {
        for (digits = 1; digits <= 9; digits += 1) {
            for (range = 1; range <= 9; range += 1) {
                array = createRandomArray(items, digits, range);
                length = array.length;
                numbers = [...array];
                RadixSort();
                array.sort((a, b) => a - b);
                if (array.join(",") !== numbers.join(",")) {
                    log("==============================");
                    log("Test failed.");
                    log("Items = "+length)
                    log("Max digits = "+digits)
                    log("Digit range = "+range)
                    log("- Result --------------------")
                    numbers.forEach(n => log(n))
                    log("- Expected ------------------")
                    array.forEach(n => log(n) )
                    return
                }
            }
        }
    }
    log("All passed")
}
test();

---

Style and syntax.

• Only capitalise variables if they are functions that are intended to be instantiated via the new token. Note the syntax highlighting.

  function MyObj(){}   // good
  var obj = new MyObj();
  
  function myObj(){}   // bad
  var obj = new myObj();
  
  function doSomething(){} // good
  
  function DoSomething(){} // bad
  
  var myData = []; // good
  
  var MyData = []; // bad.
  

• Don't take shortcuts when it comes to syntax, especial concerning curly braces when defining blocks, it is a major source of syntax related bugs that are very hard to find when you are staring at thousands of lines of code.

  for(i = 0; i < 10; i+= 1) 
      doSomethif();            // bad
  
  for(i = 0; i < 10; i+= 1) doSomethif();  // better but still bad
  
  for(i = 0; i < 10; i+= 1) {  doSomethif(); }  // OK
  
  for(i = 0; i < 10; i+= 1) {    // Good
      doSomethif(); 
  }
  

  Same for if, while, do statement blocks.

• Layout. Don't spread out initialization code throughout the source. You are making calls to clear and radixSort intermixed within the source. Ok maybe for a short bit of code but when your code gets over a few pages it can be very hard to see what is going on.

  The general layout is Function declarations first, then variables, and then functional source. I personally use bottom up layout style. The deepest level function first, top of the page, then down the page to the highest level function. So in most cases you know that to locate a function being called from within another is to look above the current functions location.

  You can also use top down, it does not matter which direction, just as long as you are consistent.

• Naming. Use clear descriptive words or phrases for the functions. You have Clear. Clear what, maybe resetBuckets would be a better name for the function.

• Use ES6. There is no reason not to use Javascript latest and best incarnation. Using ES5 because it has more browsers that support it is only shooting your self in the foot. Time moves along and ES6 will soon be ES7. As a programmer you can not afford to not learn the latest and best, by the time you know it back to front, it will be obsolete.

• Use const for any variables the will not change. (not a must, but it makes you look more professional) The general accepted reasoning between the use of constants const, block scope let, and function scope var variables is mostly about reducing bugs by protecting state. You cant mess up the state of the code if it is a protected 'const' or inaccessible (out of scope), which makes sense, well kind of, if you feel that you need the training wheels down that is.

  Understand what the differences are and use them correctly. Really it is a joke that const was added to ES6, as it is borrowed from the compiled language world, where consts are there to improve speed and access, not to protect state. Don't get me started on let. End rant.

  I use const because I hope one day the browsers will give a performance boost for const (sadly not yet) and as it does not decrease performance it is a bit of future optimization. I never use let because it is just wrong in Javascript.

---

Code

• Keep the global name-space (scope) clean. You have polluted the global name-space with some nasty variable names that are going to clash, length, numbers, clear are very common variable names and if you are on a page that shares Javascript and any of that code is slack your code will stop working. Finding out why your code suddenly stops working is next to impossible, so expose only what you must and hide the rest behind your functions scope.

  Example of clean namespace code:

  // pass to the function data
  function radixSort(numArray){
      // define required functions within the function
      function Clear() {
          for (var i = 0; i < 10; i++)
              buckets[i] = [];
      }
      // declare inside the function
      var length = numArray.length;
      var buckets = new Array(10);
  
      // return the processed information
      return sorted
  
      // Or leave in place but still return the array
      return numArray
   }
  

• Don't use new Array() and new Object() when creating objects and arrays, they are not quite the same as using literals [] for array and {} for object. The same applies to strings (if you're ever tempted) don't use = new String("my string"); use = "my string";

  I know that there is no easy way to create an array of predetermined size easily when using literal declaration, but the little bit of extra code is usually needed anyway.

• Don't delete or dereference if it can be avoided. Javascript runs in a managed environment, if you don't need something you just throw it way and it will be cleaned up for you. When you need memory it is there (well within limits). But all that cleaning up the managed code does for you does not come for free. If you are a messy coder there is a lot more work for the GC (garbage collector) to do. If you want some new memory, and it is a mess, then you don't get it until it is been cleaned up. This can become very noticeable as GC is blocking.

  So always keep that in mind when coding in any managed environment.

  Example:

  // bad
  function clear() {
      for (var i = 0; i < 10; i++) {
          buckets[i] = []; // dereferences the array held in [i] and creates a brand new one
      }
  }
  
  // good
  function clear() {
      for (var i = 0; i < 10; i++) {
          buckets[i].length = 0; // reduces the array size but does not create a new one
      }
  }
  
  // great by hard work
  // first array item is the current number of usable items in the array
  function clear() {
      for (var i = 0; i < 11; i++) {
          buckets[i][0] = 0; // totally clean nothing created, nothing deleted, and very fast
                         // but you can no longer use bucket[i].length.
      }
  }
  

• Don't repeat code. You have the function copyToArray and at the bottom of radixSort the very same code, done twice. If you want to change something you have to do it twice, and if it is a long bit of code, you may forget one.

• Don't repeat calculations. You have:

  // Bad
  for (var index = 0; index < length; index++) {
      var tenIndex = Math.pow(10, count); // recalculating the same number for each array item. Bad
      //... blah blah
  }
  count++
  
  // Good
  var tenIndex = Math.pow(10, count); // only once
  for (var index = 0; index < length; index++) {
      //... blah blah
  }
  count++
  

• Use the correct function appropriately. parseInt is for parsing integer values into Javascript's floating point numbers. It IS NOT how you remove the fractional part of a number. Use Math.floor, Math.ceil or Math.round. Some may suggest using bitwise operators to trim of the fraction var num = myNum | 0; Don't unless you understand the difference between a double and a signed int 32 and why that will make the the test runs fail.

The radixSort

Part of its beauty is that it is a very quick sort as you only need to iterate the numbers array once for each digit in the biggest number. But there is also another optimisation you missed. Numbers that are smaller than the current digit are already sorted and thus do not need to be iterated over again and can be removed from the array of values to be sorted. This give a huge performance boost.

Note that I expect that the numbers are correctly formatted as unsigned integers and no exponent notation (e.g. 127e10).

Thus the rewrite:

// One  function name so no global scope pollution.
// lower-case as this is a function rather than an object
// Pass the array of numbers rather than use a global.
// Returns a new array of numbers sorted.
function radixSort (numbers) {
    function emptyBuckets () {          // empties buckets and adds contents back to workArray
        workArray.length = 0;
        for (i = 0; i < 10; i += 1) {   // could have used buckets forEach but this is quicker on average
            if(buckets[i].length > 0){
                workArray.push(...buckets[i]);
                buckets[i].length = 0;
            }
        }
    }
    var i;                  // hoist declarations 
    const results = [];     // array that holds the finnal sorted numbers
    const buckets = [[], [], [], [], [], [], [], [], [], []];  // buckets
    const workArray = [...numbers]; // copy the numbers
    var power = 0;                  // current digit as a power of ten
    var tenPow = 1;                 // ten to the power of power
    if(numbers.length <= 1){        // if one or no items then dont sort
        return workArray;           // dont sort if there is no need.
    }
    // as numbers are sorted and moved to the result array the numbers 
    while (workArray.length > 0) {
        for (i = 0; i < workArray.length; i += 1) { // for all numbers still being sorted
            if (workArray[i] < tenPow) {            // is the number samller than the current digit
                results.push(workArray[i]);         //Yes it is sorted then remove a put o nthe result array
            } else {
                // add to bucket. Use Math.floor and save complexity doing it in one statement line
                buckets[Math.floor(workArray[i] / tenPow) % 10].push(workArray[i]);
            }
        }
        power += 1;
        tenPow = Math.pow(10, power);        
        emptyBuckets();
    }
    return results;
}

Answer 2

I am not JavaScript expert, still working on. Just share some tips.

Things to improve

1. I read Testable JavaScript and learned a few thing about choosing good test case for your code.

   Test case:

   var numbers = [90, 46, 7, 12, 100, 68]
   

   So many magic numbers, try to simplify. I came out the short one with fewer digits (only 1,2):

   var numbers = [12, 21, 1]
   

2. Make it instructional. Use this one to go over the radix sort, core of algorithm, make the transition smoothly using the customized test case.

3. Argue that the algorithm is so good, marketing the ideas to sell it:

   Here is the test case I figured out best so far:

   var numbers = [12, 21, 1]
   

   First, sort rightmost digit, \$[12,21,1]\$ will be sorted as \$[21,1,12]\$ (the first one will be the last one, since the sorting is based on 3 digits: \$2, 1,1\$, and then, sort the array on the second rightmost digit:\$ 2, 0, 1, [21,1,12] \$ will be sorted to \$[1,12,21]\$. The iterations only have 2 steps, why chooses 3 steps test case if 2 steps are good enough. Only use buckets first 3 slots of the array to illustrate the problem, so digits are 1 and 2 only. Do not spread too many, focus on the algorithm, cut time short.

4. Use meaningful variable name.

5. Separation of responsibility

   1. The function CopyToArray does two things: copy data, and also clear data. Separate two functions.

   2. RadixSort function - move Console.log to another function.

6. Add some comment to help reader warmup radix sort, for example, I explain the algorithm using customized test case.

Highlights of great things in the code:

1. Using buckets[10] is a such a great efficient idea to implement. I struggled over 4 hours to understand geeksforgeeks.com solution, wrote a Julia coding blog; and I have to come back to review the workout after 6 months, find better idea. This buckets[10] used for intermediate results are easy to understand.

Extra on JavaScript - Revealing module pattern

Read an article or take a course from pluralsight.com like Structuring JavaScript, using revealing module pattern to make the radix sort as a standalone .js file. I did some practice and very easy to pick up, and also wrote a blog Pluralsight: Structuring JavaScript.

Here is the html code I tested using Google Chrome. The revealing module object RadixSort_RevealingModule implements the radix sorting algorithm.

 <!DOCTYPE html> 
 <body> 
 <script>
    var RadixSort_RevealingModule = function () {

        var DIGIT_10 = 10;
        //var buckets = new Array(DIGIT_10);

        RadixSort = function RadixSort(testCase, buckets) {
            var maxElement = Math.max.apply(null, testCase);
            var maxDigits = GetDigitsCount(maxElement);
            var count = 0;

            var length = testCase.length;
            var numbers = testCase;
            while (count < maxDigits) {
                var divisor = Math.pow(10, count);
                for (var index = 0; index < length; index++) {                        
                    var remNumber = parseInt(numbers[index] / divisor, DIGIT_10);
                    var digit = remNumber % DIGIT_10;

                    buckets[digit].push(numbers[index]);
                }

                if (count == maxDigits - 1)
                    break;

                CopyBucketToNumber(numbers);
                ClearBucket();
                count++;
            }
        };

        function GetDigitsCount(number) {
            var count = 0;
            while (number > 0) {
                number = parseInt(number / 10);
                count++;
            }

            return count;
        }

        /*
           Radix sort: 
           Sort most insignificant digit first, and then, move to next   

           digit to the left.

           The function is to save the previous result to current, 

           for next iteration. Actually, the sorting result is in 

           buckets (kind of jagged array), go through one by one, if it 

           is not empty, output to the one dimension array. 

           Go over the test case customized for instructional purpose: 

           var testCase = [12, 21, 1];

           First iteration, sort the rightmost insignificant digit, 

           buckets[0] ={},  buckets[1] ={21, 1}, buckets[2] = {12}. 

           The following function will retrieve the result from buckets[10] 

           and build a one-dimension array, {21,1,12}

           Next iteration: 

           Sort second one next to rightmost, from {21,1,12}, buckets clear 

           first,  and then, populate with:

           buckets[0]={1}, buckets[1]={12}, buckets[2]={21}, and then, 

           output to one dimensional array: {1, 12, 21}
         */

        function CopyBucketToNumber(numbers) {
            var k = 0;
            for (var i = 0; i < DIGIT_10; i++) {
                var bucket = buckets[i];
                var length = bucket.length;
                for (var j = 0; j < length; j++) {
                    numbers[k++] = bucket[j];
                }
            }
        }

        function ClearBucket() {
            for (var i = 0; i < DIGIT_10; i++) {
                buckets[i] = [];
            }
        }

        return {
            RadixSort: RadixSort
        };
    }();
</script>      
<p>Click the button to perform radix sort.</p>

<button onclick="RadixSortDemo()">Radix Sort</button>

<p id="ArrayOutput"></p>
<script>
        var testCase = [12, 21, 1];
        document.getElementById("ArrayOutput").innerHTML = testCase;

        var buckets = new Array(10);
        function RadixSortDemo() {                
            Initialization();
            function Initialization() {
                for (var i = 0; i < 10; i++)
                    buckets[i] = [];
            }

            RadixSort_RevealingModule.RadixSort(testCase, buckets);
            document.getElementById("ArrayOutput").innerHTML = buckets;
        }
   </script>
</body>