##Your Code is not finished.
>note was called away before proof reading this answer, I will return shortly to fixup.
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
###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-- > 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();
Back to the code.
###Style and syntax.
- Only capitalise variables if they are functions that are intended to be instantiated via the new token.
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.
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
clearandradixSortintermixed 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 of phrases for the functions. You have
Clear? Clear what, mayberesetBucketswould be a better name for the functionUse 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
constfor any variables the will not change. (not a must, but it make you look more professional) The general accepted reasoning between the use of constantsconst, block scopelet, and function scopevarvariables is mostly about reducing bugs by protecting state. You cant mess up the state of the code if its 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 its is a joke thatconstwas 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. Dont get me started onletend 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 its a bit future optimization. I never use let because it is just wrong.
###Code
- Keep the global (scope) name-space clean. You have polluted the global name-space with some nasty variable names that are going to clash,
length,numbers,clearare very common variable names and if you are on a page that shares Javascript if any of that code is slack your code will stop working. Finding out why it does is next to impossible, so expose only what you must and hide the rest behind your function.
// 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()andnew 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 don't use= new String("my string");use"my string";
I know that there is no easy way to create a array of predetermined size easily when using literal declaration, but the little bit of extra code is usually needed anyway.
- Don't delete, 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 its is there (well within limits). But all that cleaning up the is managed 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 its a mess, then you don't get it until its been cleaned up.
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, no need now if you want to change something you have to do it twice, and if its 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.
parseIntis for parsing integer values into Javascripts floating point numbers. It IS NOT how you remove the fractional part of a number. UseMath.floor,Math.ceilorMath.round. Some may suggest using bitwise operators to trim of the fractionvar num = myNum | 0;Don't unless you understand the difference between adoubleand asigned int 32` and why that will make the the test 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.
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;
}