VietMX Staff asked 3 years ago
Radix sort is a sorting technique that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order. Radix sort uses counting sort as a subroutine to sort an array of numbers. Because integers can be used to represent strings (by hashing the strings to integers), radix sort works on data types other than just integers.
Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For example, a binary system (using numbers 0 and 1) has a radix of 2 and a decimal system (using numbers 0 to 9) has a radix of 10.
Radix sorts can be implemented to start at either the most significant digit (MSD) or least significant digit (LSD). For example, with 1234, one could start with 1 (MSD) or 4 (LSD).
Assume the input array is [123, 2, 999, 609, 111]:
- Based on the algorithm, we will sort the input array according to the one’s digit (least significant digit, LSD):
[0]:
[1]: 111
[2]: 002
[3]: 123
[4]:
[5]:
[6]:
[7]:
[8]:
[9]: 999, 609 // Note that we placed 999 before 609 because it appeared first.- Now, we’ll sort according to the ten’s digit:
[0]: 609, 002
[1]: 111
[2]: 123
[3]:
[4]:
[5]:
[6]:
[7]:
[8]:
[9]: 999- Finally , we sort according to the hundred’s digit (most significant digit):
[0]: 002
[1]: 111, 123
[2]:
[3]:
[4]:
[5]:
[6]: 609
[7]:
[8]:
[9]: 999
Radix sort will operate on n d-digit numbers where each digit can be one of at most b different values (since b is the base (or radix) being used). For example, in base 10, a digit can be 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9.
Radix sort uses counting sort on each digit. Each pass over n d-digit numbers will take O(n + b) time, and there are d passes total. Therefore, the total running time of radix sort is O(d(n+b)). When d is a constant and b isn’t much larger than n (in other words, b=O(n)), then radix sort takes linear time.
The space complexity comes from counting sort, which requires O(n+b) space to hold the counts, indices, and output lists.
/* Radix Sort implementation in JavaScript */
function radixSort(arr) {
var maxDigit = getMaxDigitLen(arr);
//Looping for every digit index from leftmost digits to rightmost digits
for (var i = 1; i <= maxDigit; i++) {
// rebuild the digit buckets according to this digit
var digitBuckets = [];
for (var j = 0; j < arr.length; j++) {
var digit = getDigit(arr[j], i); //get the i-th digit of the j-th element of the array
digitBuckets[digit] = digitBuckets[digit] || []; //If empty initialize with empty array
digitBuckets[digit].push(arr[j]); //Add the number in it's respective digits bucket
}
// rebuild the array according to this digit
var index = 0;
for (var k = 0; k < digitBuckets.length; k++) {
if (digitBuckets[k] && digitBuckets[k].length > 0) {
for (j = 0; j < digitBuckets[k].length; j++) {
arr[index++] = digitBuckets[k][j];
}
}
}
}
return arr;
}
// helper function to get the last n-th(position) digit of a number
var getDigit = function(num, position) {
var num_length = num.toString().length;
if (num_length < position)
return 0;
var radixPosition = Math.pow(10, position - 1); //number with the positions-th power of 10
/*
Logic: To find the 2nd digit of the number 123
we can divide it by 10, which is 12
and the using the modulus operator(%) we can find 12 % 10 = 2
*/
var digit = (Math.floor(num / radixPosition)) % 10;
return digit;
};
// helper function get the length of digits of the max value in this array
var getMaxDigitLen = function(arr) {
var maxVal = Math.max.apply(Math, arr); //Finding max value from the array
return Math.ceil(Math.log10(maxVal));
};