Sorting Arrays of Objects in JavaScript with Radix Sort

So far we’ve been sorting arrays of unsigned integers in JavaScript. This is useful at times. Sorting objects based on an embedded unsigned integer field is useful in many more cases. For instance, you have an array of objects, each holding a persons name and an id. Sorting this array by id’s using JavaScript’s built-in sorting is done as follows:

function compareIDs(a, b) { return a.id - b.id; }

function javaScriptSortingObjectsExample()
{
   const people = [
      { person: 'George', id: 2},
      { person: 'Alexa',  id: 4},
      { person: 'David',  id: 1}
   ];
   console.log(people.sort(compareIDs));
}

Note the use of a custom comparison function (compareIDs), which is used to compare numeric field (id) being sorted by. Sorting using LSD Radix Sort is shown below:

function getKey(elementA) { return elementA.id; }

function javaScriptSortingObjectsExample()
{
   const people = [
      { person: 'George', id: 2},
      { person: 'Alexa',  id: 4},
      { person: 'David',  id: 1}
   ];
   console.log(radixSortLSD(people, getKey));
}

Note the custom function (getKey), which provides access to the numeric value being sorted by.

Both methods produce the same results, for this example. Note how similar the two methods are. The built-in JavaScript sort requires a custom comparison function (compareIDs) to sort integers correctly. The Radix Sort requires a simple custom function (getKey) to access the numeric element within the object being sorted by.

Performance

I’ll provide performance comparison shortly. For now, I’ll just say that Radix Sort is faster than the built-in JavaScript sort, by 30-50%, which is not as dramatic of a speedup as for sorting purely unsigned integer arrays.

Because each object holds more data than just numbers, the Chrome browser runs out of memory at smaller array size – around 10 million elements.

Stability

One advantage that LSD Radix Sort provides is stability. If you have numerical values being sorted by, such as id’s above, and these can be duplicates, then most likely you’ll care about stability. For further discussion on stability see my blog entry Stable Sorting in JavaScript

Source Code

Below is the source code for the modified LSD Radix Sort algorithm implementation which can sort objects. Surprisingly, it’s a tiny modification to the algorithm provided in my blog entry Faster Sorting in JavaScript

function radixSortLSD(_input_array, getKey)
{
    var numberOfBins = 256;
    var Log2ofPowerOfTwoRadix = 8;
    var _output_array = new Array(_input_array.length);
    var count = new Array(numberOfBins);
    var _output_array_has_result = false;
    var bitMask = 255;
    var shiftRightAmount = 0;
    var startOfBin = new Array( numberOfBins );
    var endOfBin   = new Array( numberOfBins );

    while( bitMask != 0 )    // end processing digits when all the mask bits have been processed and shifted out, leaving no bits set in the bitMask
    {
        for (var i = 0; i < numberOfBins; i++ )
            count[ i ] = 0;
        for (var _current = 0; _current < _input_array.length; _current++ )    // Scan the array and count the number of times each digit value appears - i.e. size of each bin
            count[ extractDigit( getKey(_input_array[ _current ]), bitMask, shiftRightAmount ) ]++;
        startOfBin[ 0 ] = endOfBin[ 0 ] = 0;
        for( var i = 1; i < numberOfBins; i++ )
            startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ];
        for ( var _current = 0; _current < _input_array.length; _current++ )
            _output_array[ endOfBin[ extractDigit( getKey(_input_array[ _current ]), bitMask, shiftRightAmount ) ]++ ] = _input_array[ _current ];
        bitMask <<= Log2ofPowerOfTwoRadix;
        shiftRightAmount += Log2ofPowerOfTwoRadix;
        _output_array_has_result = !_output_array_has_result;
        var tmp = _input_array, _input_array = _output_array, _output_array = tmp;    // swap input and output arrays
    }
    if ( _output_array_has_result )
        for ( var _current = 0; _current < _input_array.length; _current++ )    // copy from output array into the input array
            _input_array[ _current ] = _output_array[ _current ];
    return _input_array;
}

The modification is the addition of getKey function. The rest of the code is the same as was used for sorting arrays of unsigned integers.

GitHub repository of all the code with usage examples

Enjoy, and let me know if it’s been helpful.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s