Implemented a Radix Sort which sorts a list of numbers. Here is my code:
function getDigit(number, index, lengthOfLongestNumber) {
let numberString = number.toString();
numberString = numberString.padStart(lengthOfLongestNumber, '0');
return parseInt(numberString[index], 10) || 0;
}
function getLengthOfLongestNumber(numbers) {
// return Math.floor(Math.log10(Math.max(...numbers))) + 1;
let largestNumber = 0;
for (let i = 0; i < numbers.length; i++) {
if (numbers[i] > largestNumber) {
largestNumber = numbers[i];
}
}
return largestNumber.toString().length;
}
function radixSort(numbers) {
const lengthOfLongestNumber = getLengthOfLongestNumber(numbers);
for (let i = lengthOfLongestNumber - 1; i >= 0; i--) {
const buckets = new Array(10).fill().map(() => []);
while (numbers.length) {
const number = numbers.shift();
buckets[getDigit(number, i, lengthOfLongestNumber)].push(number);
}
for (let j = 0; j < 10; j++) {
// numbers = numbers.concat(buckets[j]); ---> uncomment this line and comment out the following while loop
// numbers = [...numbers, ...buckets[j]]; ---> or uncomment this line and comment out the following while loop
while (buckets[j].length) {
numbers.push(buckets[j].shift());
}
}
}
return numbers;
}
Tests fail when I merge buckets array into numbers array using concat() in radixSort function (inside inner for loop). But it somehow passes if I use while loop instead.
You can see and run tests in CodeSandbox.
Why is this happening? What is the difference between them that causes tests fail?
For the returned array it doesn't matter which of those alternatives you use, but if the tests expect you to sort the given array, so that after the call the input array has been sorted itself, then indeed, the commented-out alternatives will not work. This is because those alternatives assign to numbers instead of mutating it.
Just check the difference between the alternatives when ignoring the returned array, but looking at the given array:
let arr = [521, 219, 100, 422, 889, 529, 491, 777, 641, 882, 229];
radixSort(arr);
console.log(arr);
The commented-out alternatives will log an empty array.
The correct version mutates numbers, and does not assign a (new) array to it.
To avoid the loop, you can do this mutation also like this:
numbers.push(...buckets[j]);
And you can even replace the for loop around that statement, with just this line:
numbers.push(...buckets.flat());