Radix sort implementation in JS (LSD)

Question

I have written LSD radix sort implementation in JavaScript (6 functions in total).

It sorts positive and negative integers:

// returns [-4935, -511, 1, 48, 333, 689] radixSort([-511, -4935, 333, 689, 1, 48]); 

Could you please review it?

I prefixed my concerns with: "Concern".

Performance figures sneak peek:

// 100k elements, range: -10k to 10k // Node v8.9.0 radixSort(): 136.767ms Array.prototype.sort(): 72.909ms 

---

1. Full code and tests

Run the code snippet below to test it.

Tests:

• run 100 times: generate 1k integers between -10k and 10k, sort them with radixSort() and compare the results to Array.prototype.sort()
• compare execution times of radixSort(), Array.prototype.sort() and otherRadixSort() for 100k integers between 0 and 10k (other implementation found on GitHub).
• test each function

/** @module */ /** * Get the nth digit from a number. * Rounds the number (12.5 -> 13). * Returns 0 when the specified index is out of range. * @example * // returns 4 * getDigit(1234, 0); * @see {@link https://stackoverflow.com/a/7784664 Get digits out of a number} * @param {Number} num Number * @param {Number} [index=0] The index of the number's digit to return. * Digits are zero-indexed from right to left. * @returns {Number} The digit of a number at specified index. */ function getDigit(num, index = 0) { let idx = index; let number = Math.round(num); let remainder = 0; let lastIteration = false; // best condition: (index >= 0 && index =< number.length) while (idx >= 0) { remainder = (number % 10); number = ((number - remainder) / 10); if (lastIteration) { break; } /** * If the passed index is bigger than the number's length, * make only one unnecessary loop to return 0. * i.e `getDigit(900, 50)` should return 0 after 4 loops instead 50. */ if (number === 0) { // if we stopped here, `getDigit(900, 50)` would return 9. lastIteration = true; } idx -= 1; } return remainder; } /** * Create an array of X empty arrays. * @example * const buckets = createBuckets(10); * // returns 10 * buckets.length * // returns true * Array.isArray(buckets[9]); * @param {Number} x Number of arrays to create * @returns {Array} Array of arrays. */ function createBuckets(x) { // `new Array(10).fill([])` would reference the same Array object const buckets = new Array(x); // `Array.forEach()` ignores array holes for (let i = 0; i < buckets.length; i += 1) { buckets[i] = []; } return buckets; } /** * Sort positive integers using nth digit/exponent. * @example * const integers = [1020, 680, 870, 90, 1]; * // sort by 10's place * const sorted = sort(integers, 1); * // returns [1, 1020, 870, 680, 90] * console.log(sorted); * @param {Array} intgs Array of positive integers * @param {Number} [nth=0] Digit/exponent * @returns {Array} Sorted array of integers by nth digit. */ function sort(intgs, nth = 0) { if (intgs.length === 0) { return intgs; } const integers = [...intgs]; const currentPlaceValue = 10 ** nth; const buckets = createBuckets(10); const sorted = []; // add number to bucket or skip it if it's sorted integers.forEach((integer) => { /** * If we're sorting the integers using 2nd digit (10's place), * integers have been already sorted by LSD (1's place). */ if (integer >= currentPlaceValue) { const digit = getDigit(integer, nth); buckets[digit].push(integer); } else { sorted.push(integer); } }); // empty each bucket into the auxiliary array buckets.forEach((bucket) => { if (bucket.length > 0) { sorted.push(...bucket); } }); // copy elements back from the auxiliary to original array sorted.forEach((item, j) => { if (item !== integers[j]) { integers[j] = item; } }); return integers; } /** * Count digits of a positive or negative number. * @example * // returns 3 * countDigits(-124.785); * @see {@link https://stackoverflow.com/a/28203456 Count digits of a number} * @param {Number} number Number * @returns {Number} Number of digits. */ function countDigits(number) { const abs = Math.abs(number); // how many 10s have to be multiplied to get `abs` const log10 = Math.log10(abs); // `Math.log10(0)` returns `-Infinity` const finite = Number.isFinite(log10) ? log10 : 0; const floor = Math.floor(finite); // `Math.ceil(0) = 0` vs `Math.floor(0) + 1 = 1` (correct count) const count = (floor + 1); return count; } /** * Find the biggest integer in the array of integers. * @example * // returns 150 * getMax([-150, 100]); * @param {Array} integers Array of integers * @returns {Number} The biggest integer from the array. */ function getMax(integers) { const absArr = integers.map(Math.abs); const maxNum = Math.max(...absArr); return maxNum; } /** * LSD radix sort that sorts positive and negative integers. * @static * @example * import radixSort from './radixSort'; * const integers = [-511, -4935, 333, 689, 1, 48]; * const sorted = radixSort(integers); * // returns [-4935, -511, 1, 48, 333, 689] * console.log(sorted); * @see {@link https://en.wikipedia.org/wiki/Radix_sort#Least_significant_digit_radix_sorts Wiki: LSD radix sort} * @see {@link https://codereview.stackexchange.com/a/150288 Radix sort implementation in JS} * @param {Array} integers Array of integers * @returns {Array} The sorted array. */ function radixSort(integers) { const maxInteger = getMax(integers); const digits = countDigits(maxInteger); let positiveIntegers = integers.filter(v => v >= 0); let negativeIntegers = integers.filter(v => v < 0).map(Math.abs); // sort the integers starting at the LSD (ones, next tens, then hundreds...) for (let i = 0; i < digits; i += 1) { positiveIntegers = sort(positiveIntegers, i); negativeIntegers = sort(negativeIntegers, i); } // reverse the sorted negative integers, add the negative sign to each integer negativeIntegers = negativeIntegers.reverse().map(v => -Math.abs(v)); // merge the positive and negative integers const results = negativeIntegers.concat(positiveIntegers); return results; } // Tests // Test functions // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random#Getting_a_random_integer_between_two_values_inclusive function getRandomIntInclusive(min, max) { min = Math.ceil(min); max = Math.floor(max); return Math.floor(Math.random() * (max - min + 1)) + min; } // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort function compareNumbers(a, b) { return a - b; } function generateArrayIntegers(length, min, max) { return Array.from({ length: length }, () => getRandomIntInclusive(min, max)); } // Mocha mocha.setup('bdd'); const { expect } = chai; describe('Radix Sort', function() { describe('radixSort()', function() { it('Sorts the array of 1k integers between -10k and 10k', () => { for (let i = 100; i >= 0; i -= 1) { const generated = generateArrayIntegers(1000, -10000, 10000); const result = radixSort(generated); generated.sort(compareNumbers); expect(result).to.deep.equal(generated); } }); }); describe('sort([1020, 680, 870, 90, 1], 1)', () => { it('Sort the integers by 10\'s place', () => { const result = sort([1020, 680, 870, 90, 1], 1); expect(result).to.deep.equal([1, 1020, 870, 680, 90]); }); }); describe('getDigit(1234, 1)', () => { it('Gets the nth digit from a number', () => { const result = getDigit(1234, 1); expect(result).equal(3); }); }); describe('getDigit(12.5, 0)', () => { it('Rounds the number then gets the nth digit', () => { const result = getDigit(12.5, 0); expect(result).equal(3); }); }); describe('getDigit(10, 3)', () => { it('Returns 0 when the specified index is out of range', () => { const result = getDigit(10, 3); expect(result).equal(0); }); }); describe('countDigits(12345)', () => { it('Counts digits of the number', () => { const result = countDigits(12345); expect(result).equal(5); }); }); describe('countDigits(-65)', () => { it('Counts digits of the negative number', () => { const result = countDigits(-65); expect(result).equal(2); }); }); describe('countDigits(0)', () => { it('Counts digits properly when the number is 0', () => { const result = countDigits(0); expect(result).equal(1); }); }); describe('getMax([-150, 100, 50])', () => { it('Finds the biggest absolute number in the array', () => { const result = getMax([-150, 100, 50]); expect(result).equal(150); }); }); describe('createBuckets(10)', () => { it('Create buckets array in which each bucket is an empty array itself', () => { const result = createBuckets(10); expect(result).to.have.lengthOf(10); for (let i = 0; i < result.length; i += 1) { expect(result[i]).to.be.an('array').that.is.empty; } }); }); }); mocha.run(); /** * Time * * Measure execution times for this and other implementation (to compare). * Other implementation: https://github.com/mgechev/javascript-algorithms/blob/master/src/sorting/radixsort.js */ const generated = generateArrayIntegers(100000, 0, 10000); const otherRadixSort = window.radixSort; console.time('radixSort()'); radixSort(generated); console.timeEnd('radixSort()'); console.time('otherRadixSort()'); otherRadixSort(generated); console.timeEnd('otherRadixSort()'); console.time('Array.prototype.sort()'); generated.sort(compareNumbers); console.timeEnd('Array.prototype.sort()');

<script src="https://rawgit.com/mgechev/javascript-algorithms/master/src/sorting/radixsort.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/chai/4.1.2/chai.min.js"></script> <link href="https://cdnjs.cloudflare.com/ajax/libs/mocha/4.0.1/mocha.min.css" rel="stylesheet"/> <script src="https://cdnjs.cloudflare.com/ajax/libs/mocha/4.0.1/mocha.min.js"></script> <div id="mocha"></div>

---

2. Isolated code - 6 functions

The code consists of 6 functions, the hierarchy is following:

• radixSort() - the main function
  • getMax() - find the biggest integer
  • countDigits() - how many digits the number has
  • sort() - the heart, sort an array using nth digit (ones, tens...)
    • createBuckets() - create array of empty arrays
    • getDigit() - get the nth digit from a number

radixSort() - the main

• Find the biggest integer, count its digits.
• Split the passed integers into two arrays: positive and negative (for negatives get the absolute value).
• Sort both arrays for each digit.

• Reverse the sorted negative array, add negative sign, return them both merged.

  function radixSort(integers) { const maxInteger = getMax(integers); const digits = countDigits(maxInteger); let positiveIntegers = integers.filter(v => v >= 0); let negativeIntegers = integers.filter(v => v < 0).map(Math.abs); // sort the integers starting at the LSD (ones, next tens, then hundreds...) for (let i = 0; i < digits; i += 1) { positiveIntegers = sort(positiveIntegers, i); negativeIntegers = sort(negativeIntegers, i); } /** reverse the sorted negative integers, * add the negative sign to each integer */ negativeIntegers = negativeIntegers.reverse().map(v => -Math.abs(v)); // merge the positive and negative integers const results = negativeIntegers.concat(positiveIntegers); return results; } 

getMax()

Concern 1: I use .map(Math.abs) twice: in getMax() and radixSort().

/** * Find the biggest integer in the array of integers. * @example * // returns 150 * getMax([-150, 100]); * @param {Array} integers Array of integers * @returns {Number} The biggest integer from the array. */ function getMax(integers) { const absArr = integers.map(Math.abs); const maxNum = Math.max(...absArr); return maxNum; } // returns 150 console.log(getMax([-150, 100]));

countDigits()

/** * Count digits of a positive or negative number. * @example * // returns 3 * countDigits(-124.785); * @see {@link https://stackoverflow.com/a/28203456 Count digits of a number} * @param {Number} number Number * @returns {Number} Number of digits. */ function countDigits(number) { const abs = Math.abs(number); // how many 10s have to be multiplied to get `abs` const log10 = Math.log10(abs); // `Math.log10(0)` returns `-Infinity` const finite = Number.isFinite(log10) ? log10 : 0; const floor = Math.floor(finite); // `Math.ceil(0) = 0` vs `Math.floor(0) + 1 = 1` (correct count) const count = (floor + 1); return count; } // returns 3 console.log(countDigits(-124.785));

sort() - the heart

integers array -> each integer -> buckets[digit] -> empty buckets contents to sorted array -> copy elements from sorted to integers

It expects only positive integers but the main function radixSort() takes care of that.

Concern 2: it creates the same buckets array every loop. It could be passed and cleared every loop with buckets.splice(0). On the other hand, GC should take care of that, shouldn't it?

Concern 3: I'm using auxiliary array sorted, should it be avoided?

function sort(intgs, nth = 0) { if (intgs.length === 0) { return intgs; } const integers = [...intgs]; const currentPlaceValue = 10 ** nth; const buckets = createBuckets(10); const sorted = []; // add number to bucket or skip it if it's sorted integers.forEach((integer) => { /** * If we're sorting the integers using 2nd digit (10's place), * integers have been already sorted by LSD (1's place). */ if (integer >= currentPlaceValue) { const digit = getDigit(integer, nth); buckets[digit].push(integer); } else { sorted.push(integer); } }); // empty each bucket into the auxiliary array buckets.forEach((bucket) => { if (bucket.length > 0) { sorted.push(...bucket); } }); // copy elements back from the auxiliary to original array sorted.forEach((item, j) => { if (item !== integers[j]) { integers[j] = item; } }); return integers; } 

createBuckets()

/** * Create an array of X empty arrays. * @example * const buckets = createBuckets(10); * // returns 10 * buckets.length * // returns true * Array.isArray(buckets[9]); * @param {Number} x Number of arrays to create * @returns {Array} Array of arrays. */ function createBuckets(x) { // `new Array(10).fill([])` would reference the same Array object const buckets = new Array(x); // `Array.forEach()` ignores array holes for (let i = 0; i < buckets.length; i += 1) { buckets[i] = []; } return buckets; } const buckets = createBuckets(10); // returns 10 console.log(buckets.length); // returns true console.log(Array.isArray(buckets[9]));

getDigit()

/** * Get the nth digit from a number. * Rounds the number (12.5 -> 13). * Returns 0 when the specified index is out of range. * @example * // returns 4 * getDigit(1234, 0); * @see {@link https://stackoverflow.com/a/7784664 Get digits out of a number} * @param {Number} num Number * @param {Number} [index=0] The index of the number's digit to return. * Digits are zero-indexed from right to left. * @returns {Number} The digit of a number at specified index. */ function getDigit(num, index = 0) { let idx = index; let number = Math.round(num); let remainder = 0; let lastIteration = false; // best condition: (index >= 0 && index =< number.length) while (idx >= 0) { remainder = (number % 10); number = ((number - remainder) / 10); if (lastIteration) { break; } /** * If the passed index is bigger than the number's length, * make only one unnecessary loop to return 0. * i.e `getDigit(900, 50)` should return 0 after 4 loops instead 50. */ if (number === 0) { // if we stopped here, `getDigit(900, 50)` would return 9. lastIteration = true; } idx -= 1; } return remainder; } // returns 4 console.log(getDigit(1234, 0));

Concern 4: is it efficient enough for a typical radix sort implementation in JS?

Answer 1

Well!!

First off I will say that is an impressive amount of work for a sort, lots of research and references.

BUT!!!

I am not going to sugar coat the rest. The implementation is overly complex and very inefficient, the testing touched none of the edge cases or expected failure states, and the overall design and layout of the code is chaotic and difficult to follow.

Your concerns

Concern 1: I use .map(Math.abs) twice: in getMax() and radixSort().

Yep that is a concern, First getting the max integer size even if done in a single pass adds an extra pass on the array that is not needed.

Concern 2: it creates the same buckets array every loop. It could be passed and cleared every loop with buckets.splice(0). On the other hand, GC should take care of that, shouldn't it?

The buckets would be best as a pre allocated typed array. Memory is cheap and a each bucket could have been given enough memory to hold all the values. With a counter for each bucket reset to zero for each pass, you would have eliminated all but the initial and exiting memory management overheads.

Concern 3: I'm using auxiliary array sorted, should it be avoided?

Yes and you make copies of the input array and several places that are not needed at all. The javascript Array.sort sorts in place. With the buckets the radix sort can do the same.

Concern 4: is it efficient enough for a typical radix sort implementation in JS?

No it is slow and GC unfriendly (plus the other stuff in the points above.)

Testing

Testing is how you understand your codes behaviour. You do not need to test the sub components of the logic.

If you test some random arrays of integers and compare the results to a known correct result (Array.sort) and pass you also know that each sub component works. You would not expect the sort to work yet any of the sub components to fail would you?

Testing is about the most brutal assault on the code you can imagine, What happens when I pass an array of millions zeros, or infinities, or NaN, or strings, 10e512, or random sparse items.

It does not matter if the function can cope with the garbage in. What matters is that you know what it does do and can thus document that behaviour for users of the function.

The code

Radix sort is fast, your performance tests should be getting times that are very close to Array.sort but you have complicated the sort making it impossible to match the native sort.

Buckets

You split the array into two positive and negative values (that is a partial sort and not technically part of a radix sort) The radix does not have to be just the positive digits, you can expand on that, and include 20 buckets for digits -9 to -0 and 0 to 9 that way you don't need to split the array.

Max digits?

You are passing over each value at least once, you can test the digit length as you go rather than as a separate pass. (finding the max value is also a partial sort, not part of a radix sort)

Get digit

...is very very slow and OMDG who wrote that! To get a digit from a number positive or negative. const digit = (Math.floor(Math.abs(value) / (10**place)) % 10) * Math.sign(value);

Performance

If you want speed you need to avoid array iterators like forEach, map, filter, etc as they come with baggage that can be avoided by using standard for, while and do while loops.

Don't add default parameters if you never use them as they extra noise in the source code and overhead for the CPU.

Don't copy arrays if you don't need to. You have const integers = [...intgs]; yet you overwrite the values, well almost as you do

sorted.forEach((item, j) => { if (item !== integers[j]) { // <<<<< NO!! not needed and just overhead integers[j] = item; } }); 

The following from your code requires 3 copies of the array to exist at the same time.

positiveIntegers = sort(positiveIntegers, i); 

Design

You have created a whole pile of functions, it's a real mess. Put the related functions together inside the main function.

Use closure to reduce the number of arguments you are moving about.

Don't create variable you use on once in the next line.

Deep in the sort you test for empty array, that should be the first test in the radix sort not deep inside.

A rewrite

This is an example of the same functionality as your code, and by far not the definitive solution. It matches the native sort in speed by eliminating a lot of the overhead you had. It uses 20 bucket so that the positive and negative values don't need to be split

function radixSort(array) { function sort(nth) { var i,j,k; var nextRadix = false; const currentPlaceValue = 10 ** nth; const nextPlaceValue = 10 ** (nth + 1); const buckets = [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]]; i = 0; for (j = 0; j < array.length; j++) { var val = array[j]; var uVal = Math.abs(val) if (uVal >= nextPlaceValue) { nextRadix = true } const digit = Math.floor(uVal / currentPlaceValue) % 10; if (val >= 0) { buckets[digit + 10].push(val) } else { buckets[10 - digit].push(val) } } for (j = 0; j < buckets.length; j++) { const bucket = buckets[j]; for (k = 0; k < bucket.length; k++) { array[i++] = bucket[k] } } return nextRadix; } var radix = 0; if (array.length > 1) { while (sort(radix ++)); } return array; }