Repository navigation
Expand file tree
/
Copy pathCountingSort.js
More file actions
78 lines (63 loc) 路 2.9 KB
/
Copy pathCountingSort.js
File metadata and controls
78 lines (63 loc) 路 2.9 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
import Sort from '../Sort';
export default class CountingSort extends Sort {
/**
* @param {number[]} originalArray
* @param {number} [smallestElement]
* @param {number} [biggestElement]
*/
sort(originalArray, smallestElement = undefined, biggestElement = undefined) {
// Init biggest and smallest elements in array in order to build number bucket array later.
let detectedSmallestElement = smallestElement || 0;
let detectedBiggestElement = biggestElement || 0;
if (smallestElement === undefined || biggestElement === undefined) {
originalArray.forEach((element) => {
// Visit element.
this.callbacks.visitingCallback(element);
// Detect biggest element.
if (this.comparator.greaterThan(element, detectedBiggestElement)) {
detectedBiggestElement = element;
}
// Detect smallest element.
if (this.comparator.lessThan(element, detectedSmallestElement)) {
detectedSmallestElement = element;
}
});
}
// Init buckets array.
// This array will hold frequency of each number from originalArray.
const buckets = Array(detectedBiggestElement - detectedSmallestElement + 1).fill(0);
originalArray.forEach((element) => {
// Visit element.
this.callbacks.visitingCallback(element);
buckets[element - detectedSmallestElement] += 1;
});
// Add previous frequencies to the current one for each number in bucket
// to detect how many numbers less then current one should be standing to
// the left of current one.
for (let bucketIndex = 1; bucketIndex < buckets.length; bucketIndex += 1) {
buckets[bucketIndex] += buckets[bucketIndex - 1];
}
// Now let's shift frequencies to the right so that they show correct numbers.
// I.e. if we won't shift right than the value of buckets[5] will display how many
// elements less than 5 should be placed to the left of 5 in sorted array
// INCLUDING 5th. After shifting though this number will not include 5th anymore.
buckets.pop();
buckets.unshift(0);
// Now let's assemble sorted array.
const sortedArray = Array(originalArray.length).fill(null);
for (let elementIndex = 0; elementIndex < originalArray.length; elementIndex += 1) {
// Get the element that we want to put into correct sorted position.
const element = originalArray[elementIndex];
// Visit element.
this.callbacks.visitingCallback(element);
// Get correct position of this element in sorted array.
const elementSortedPosition = buckets[element - detectedSmallestElement];
// Put element into correct position in sorted array.
sortedArray[elementSortedPosition] = element;
// Increase position of current element in the bucket for future correct placements.
buckets[element - detectedSmallestElement] += 1;
}
// Return sorted array.
return sortedArray;
}
}