Implementing RadixSort using JavaScript 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 &lt; 10; i++)
        buckets[i] = [];
}

RadixSort();
function RadixSort() {
    var maxElement = Math.max.apply(null , numbers);
    var maxDigits = GetDigitsCount(maxElement);
    var count = 0;
    while (count &lt; maxDigits) {
        CopyToArray();
        for (var index = 0; index &lt; 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 &lt; 9; i++) {
        var arr = buckets[i];
        var arrLength = arr.length;
        for (var j = 0; j &lt; arrLength; j++)
            console.log(arr[j]);
    }
}

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

function CopyToArray() {
    var k = 0;
    for (var i = 0; i &lt; 10; i++) {
        var arr = buckets[i];
        var arrLength = arr.length;
        for (var j = 0; j &lt; arrLength; j++) {
            numbers[k++] = arr[j];
        }
        buckets[i] = [];
    }
}
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:


There is no code without testing.
There is no code without testing.
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-- &gt; 0) {
            numSize = Math.random() * maxDigits;
            num = 0;
            while (numSize-- &gt; 0) {
                num *= 10;
                num += Math.floor(Math.random() * digitRange);
            }
            numbers.push(num);
        }
        return numbers;
    }
    var items, digits, range, array;
    for (items = 0; items &lt;= 20; items += 1) {
        for (digits = 1; digits &lt;= 9; digits += 1) {
            for (range = 1; range &lt;= 9; range += 1) {
                array = createRandomArray(items, digits, range);
                length = array.length;
                numbers = [...array];
                RadixSort();
                array.sort((a, b) =&gt; 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 =&gt; log(n))
                    log("- Expected ------------------")
                    array.forEach(n =&gt; 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 &lt; 10; i+= 1) 
    doSomethif();            // bad

for(i = 0; i &lt; 10; i+= 1) doSomethif();  // better but still bad

for(i = 0; i &lt; 10; i+= 1) {  doSomethif(); }  // OK

for(i = 0; i &lt; 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 &lt; 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 &lt; 10; i++) {
        buckets[i] = []; // dereferences the array held in [i] and creates a brand new one
    }
}

// good
function clear() {
    for (var i = 0; i &lt; 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 &lt; 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 &lt; 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 &lt; 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 &lt; 10; i += 1) {   // could have used buckets forEach but this is quicker on average
            if(buckets[i].length &gt; 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 &lt;= 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 &gt; 0) {
        for (i = 0; i &lt; workArray.length; i += 1) { // for all numbers still being sorted
            if (workArray[i] &lt; 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;
}