forked from mgechev/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathradixsort.js
More file actions
100 lines (87 loc) · 2.83 KB
/
Copy pathradixsort.js
File metadata and controls
100 lines (87 loc) · 2.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
(function (exports) {
'use strict';
var radixSort = (function () {
/**
* Returns the digit of a number that is 'lsdOffset'
* places from the least significant digit.
*
* @private
* @param {Number} number Number
* @param {Number} lsdOffset Offset of the digit to return, counting
* from the position of the least significant digit (e.g. lsdOffset = 0
* will return the least significant digit itself)
* @return {String} digit The specified number digit. Returns 'undefined'
* if lsdOffset is bigger or equal to the number of digits of the 'number'
* argument.
*/
var getDigit = function (number, lsdOffset) {
var size = number.toString().length;
var digit;
if (lsdOffset >= 0 && lsdOffset < size) {
digit = number.toString()[size - 1 - lsdOffset];
}
return digit;
};
/**
* Least significant digit (LSD) Radix sort. A non-comparative,
* stable integer sorting algorithm.<br><br>
* Worst-case time complexity is O(N K) for N keys with K being
* the average key length, measured in number of digits.
*
* @example
* var sort = require('path-to-algorithms/src/' +
* 'sorting/radixsort').radixSort;
* console.log(sort([2, 5, 1, 3, 4])); // [ 1, 2, 3, 4, 5 ]
*
* @public
* @module sorting/radixsort
* @param {Array} array Input integer array
* @return {Array} Sorted array
*/
return function (array) {
var size = array.length;
var R = 10; /* Alphabet size ([0-9] for integers) */
var count;
var digit;
var i;
var j;
/* Find maximum key size */
var maxKeySize = (array[0] || '').toString().length;
for (i = 1; i < size; i += 1) {
var numStr = array[i].toString();
if (numStr.length > maxKeySize) {
maxKeySize = numStr.length;
}
}
for (i = 0; i < maxKeySize; i += 1) {
/* Initialize count */
count = [];
for (j = 0; j < R; j += 1) {
count[j] = 0;
}
/* Count frequency of each array element */
for (j = 0; j < size; j += 1) {
digit = getDigit(array[j], i) || 0;
count[digit] += 1;
}
/* Compute cumulates */
for (j = 1; j < R; j += 1) {
count[j] += count[j - 1];
}
/* Move elements to auxiliary array */
var aux = [];
for (j = size - 1; j >= 0; j -= 1) {
digit = getDigit(array[j], i) || 0;
count[digit] -= 1;
aux[count[digit]] = array[j];
}
/* Copy elements back from auxilary array */
for (j = 0; j < size; j += 1) {
array[j] = aux[j];
}
}
return array;
};
})();
exports.radixSort = radixSort;
})(typeof window === 'undefined' ? module.exports : window);