##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.
###First of.
Read this [Gramma and types][1]
---
###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();
Now back to the code.
----
###Style and syntax.
- Only capitalise variables if they are functions that are intended to be instantiated via the new token. *note the syntax highlighting.*
<!-- language: lang-js -->
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 short cuts 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.
<!-- language: lang-js -->
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 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 names-space code.
<!-- language: lang-js -->
// 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 youare 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
<!-- language: lang-js -->
// 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
<!-- language: lang-js -->
// 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 (eg 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;
}
[1]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Grammar_and_types#Literals