Sorting data takes time.
In order to better understand radix sort I recommend you either read my previous post on counting sort or any documentation on how counting sort works because the LSD Radix sort is built off of counting sorts.
In most radix sorts you start by sorting the LSD (least significant digit) then moving through all the digits until you reach the (MSD) most significant digit.
The definition of Radix (or base) is the number of unique digits including 0 to represent numbers in a number system.
Binary has a radix of 2.
Hexadecimal has a radix of 16.
The Decimal system or Base-10 typical system you use daily has a radix of 10.
An LSD Radix sort can be run in JavaScript with two inputs. The first for the array to be sorted and the second for the largest number of digits in a single element of the array.
function LSDRadixSort(array, radix) {
//sets the radix to base 10 by default unless otherwise specified.
radix = radix || 10;
// Determine minimum and maximum values in the array to be sorted.
var minValue = array[0];
var maxValue = array[0];
for (var i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i];
} else if (array[i] > maxValue) {
maxValue = array[i];
}
}
var exponent = 1;
// This while loop runs a counting sort for each index in an array from
//least significant to most significant
while ((maxValue - minValue) / exponent >= 1) {
array = countingSortByDigit(array, radix, exponent, minValue);
exponent *= radix;
}
return array;
}
function countingSortByDigit(array, radix, exponent, minValue) {
var i;
var bucketIndex;
var buckets = new Array(radix);
var output = new Array(array.length);
// Initialize the bucket array
for (i = 0; i < radix; i++) {
buckets[i] = 0;
}
// Count the frequencies
for (i = 0; i < array.length; i++) {
bucketIndex = Math.floor(((array[i] - minValue) / exponent) % radix);
buckets[bucketIndex]++;
}
// Compute cumulative amounts
for (i = 1; i < radix; i++) {
buckets[i] += buckets[i - 1];
}
// Move items in the array to be sorted
for (i = array.length - 1; i >= 0; i--) {
bucketIndex = Math.floor(((array[i] - minValue) / exponent) % radix);
output[--buckets[bucketIndex]] = array[i];
}
// set output to the original array
for (i = 0; i < array.length; i++) {
array[i] = output[i];
}
return array;
}
Now radix seems complicated but if we break it down to a simple example it becomes a lot easier to understand.
Lets say that there is an array of numbers in base 10 that we want to sort
[99, 88, 2 ,33 ,79, 44, 10]
when we are in the while loop of the radix sort we would first sort by the ones place
[9, 8, 2, 3, 7, 4, 0]
//=>
[0, 2, 3, 4, 8, 9, 9]
//which makes the actual array
//=>
[10, 2, 33, 44, 88, 99, 79]
//then we sort that array by the 10's place
//=>
[0, 1, 3, 4, 7, 8, 9]
//which makes the actual array
//=>
[02, 10, 33, 44, 79, 88, 99]
This works for however many digits there are in total in the longest number for any radix be it base 2, 10 or 16.
Top comments (0)