You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
64 lines
1.3 KiB
64 lines
1.3 KiB
/**
|
|
*
|
|
*/
|
|
var RadixSort = function() {
|
|
this.instructions = [];
|
|
};
|
|
|
|
RadixSort.prototype = Object.create(Sorter.prototype);
|
|
|
|
/**
|
|
*
|
|
*/
|
|
RadixSort.prototype.sort = function(arr) {
|
|
var max = 0;
|
|
var len = arr.length;
|
|
var tmp = arr;
|
|
|
|
// Find max
|
|
for (var i = 0; i < len; i++) {
|
|
if (max < arr[i].value) {
|
|
max = arr[i].value;
|
|
}
|
|
}
|
|
|
|
// Run through digit sort for as many digits as in max
|
|
var digits = max.toString().length;
|
|
for (var i = 1; i <= digits; i++) {
|
|
tmp = this.sortByDigit(tmp, i);
|
|
}
|
|
|
|
return tmp;
|
|
};
|
|
|
|
/**
|
|
*
|
|
*/
|
|
RadixSort.prototype.sortByDigit = function(arr, digit) {
|
|
var len = arr.length;
|
|
var val = null;
|
|
var buckets = [];
|
|
var result = [];
|
|
|
|
// Sort into buckets
|
|
for (var i = 0; i < len; i++) {
|
|
// Remove more significant digits, then round down all less significant digits.
|
|
val = arr[i].value % Math.pow(10, digit);
|
|
val = Math.floor((val / Math.pow(10, digit - 1)));
|
|
|
|
if (buckets[val] === undefined) {
|
|
buckets[val] = [];
|
|
}
|
|
|
|
buckets[val].push(arr[i]);
|
|
}
|
|
|
|
// Concat sorted buckets
|
|
for (var j = 0; j < 10; j++) {
|
|
if (buckets[j] !== undefined) {
|
|
result = result.concat(buckets[j]);
|
|
}
|
|
}
|
|
|
|
return result;
|
|
};
|
|
|