forked from trekhleb/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
RadixSort.js
152 lines (131 loc) · 4.29 KB
/
RadixSort.js
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
import Sort from '../Sort';
// Using charCode (a = 97, b = 98, etc), we can map characters to buckets from 0 - 25
const BASE_CHAR_CODE = 97;
const NUMBER_OF_POSSIBLE_DIGITS = 10;
const ENGLISH_ALPHABET_LENGTH = 26;
export default class RadixSort extends Sort {
/**
* @param {*[]} originalArray
* @return {*[]}
*/
sort(originalArray) {
// Assumes all elements of array are of the same type
const isArrayOfNumbers = this.isArrayOfNumbers(originalArray);
let sortedArray = [...originalArray];
const numPasses = this.determineNumPasses(sortedArray);
for (let currentIndex = 0; currentIndex < numPasses; currentIndex += 1) {
const buckets = isArrayOfNumbers ?
this.placeElementsInNumberBuckets(sortedArray, currentIndex) :
this.placeElementsInCharacterBuckets(sortedArray, currentIndex, numPasses);
// Flatten buckets into sortedArray, and repeat at next index
sortedArray = buckets.reduce((acc, val) => {
return [...acc, ...val];
}, []);
}
return sortedArray;
}
/**
* @param {*[]} array
* @param {number} index
* @return {*[]}
*/
placeElementsInNumberBuckets(array, index) {
// See below. These are used to determine which digit to use for bucket allocation
const modded = 10 ** (index + 1);
const divided = 10 ** index;
const buckets = this.createBuckets(NUMBER_OF_POSSIBLE_DIGITS);
array.forEach((element) => {
this.callbacks.visitingCallback(element);
if (element < divided) {
buckets[0].push(element);
} else {
/**
* Say we have element of 1,052 and are currently on index 1 (starting from 0). This means
* we want to use '5' as the bucket. `modded` would be 10 ** (1 + 1), which
* is 100. So we take 1,052 % 100 (52) and divide it by 10 (5.2) and floor it (5).
*/
const currentDigit = Math.floor((element % modded) / divided);
buckets[currentDigit].push(element);
}
});
return buckets;
}
/**
* @param {*[]} array
* @param {number} index
* @param {number} numPasses
* @return {*[]}
*/
placeElementsInCharacterBuckets(array, index, numPasses) {
const buckets = this.createBuckets(ENGLISH_ALPHABET_LENGTH);
array.forEach((element) => {
this.callbacks.visitingCallback(element);
const currentBucket = this.getCharCodeOfElementAtIndex(element, index, numPasses);
buckets[currentBucket].push(element);
});
return buckets;
}
/**
* @param {string} element
* @param {number} index
* @param {number} numPasses
* @return {number}
*/
getCharCodeOfElementAtIndex(element, index, numPasses) {
// Place element in last bucket if not ready to organize
if ((numPasses - index) > element.length) {
return ENGLISH_ALPHABET_LENGTH - 1;
}
/**
* If each character has been organized, use first character to determine bucket,
* otherwise iterate backwards through element
*/
const charPos = index > element.length - 1 ? 0 : element.length - index - 1;
return element.toLowerCase().charCodeAt(charPos) - BASE_CHAR_CODE;
}
/**
* Number of passes is determined by the length of the longest element in the array.
* For integers, this log10(num), and for strings, this would be the length of the string.
*/
determineNumPasses(array) {
return this.getLengthOfLongestElement(array);
}
/**
* @param {*[]} array
* @return {number}
*/
getLengthOfLongestElement(array) {
if (this.isArrayOfNumbers(array)) {
return Math.floor(Math.log10(Math.max(...array))) + 1;
}
return array.reduce((acc, val) => {
return val.length > acc ? val.length : acc;
}, -Infinity);
}
/**
* @param {*[]} array
* @return {boolean}
*/
isArrayOfNumbers(array) {
// Assumes all elements of array are of the same type
return this.isNumber(array[0]);
}
/**
* @param {number} numBuckets
* @return {*[]}
*/
createBuckets(numBuckets) {
/**
* Mapping buckets to an array instead of filling them with
* an array prevents each bucket from containing a reference to the same array
*/
return new Array(numBuckets).fill(null).map(() => []);
}
/**
* @param {*} element
* @return {boolean}
*/
isNumber(element) {
return Number.isInteger(element);
}
}