forked from SiZapPaaiGwat/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcountingsort.js
More file actions
90 lines (83 loc) · 2.41 KB
/
Copy pathcountingsort.js
File metadata and controls
90 lines (83 loc) · 2.41 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
(function (exports) {
'use strict';
var countingSort = (function () {
/**
* Gets the count of the elements into the input array.
*
* @private
* @param {Array} array The input array.
* @return {Array} The count of each element from the input array.
*/
function getCount(array) {
var count = [];
var current;
for (var i = 0; i < array.length; i += 1) {
current = array[i];
count[current] = (count[current] || 0) + 1;
}
return count;
}
/**
* Gets the count of the elements which are less than a given.
*
* @private
* @param {Array} array The input array.
* @return {Array} less The count of the elements which.
* are less than each element from the input.
*/
function getLessCount(array) {
var less = [];
var last;
less[0] = array[0] || 0;
for (var i = 1; i < array.length; i += 1) {
last = array[i - 1] || 0;
less[i] = last + less[i - 1];
}
return less;
}
/**
* Sorts the input array.
*
* @private
* @param {Array} array Input which should be sorted.
* @param {Array} less Count of the less elements for each element.
* @return {Array} The sorted input.
*/
function sort(array, less) {
var result = [];
var currentPositions = [];
var current;
var position;
for (var i = 0; i < array.length; i += 1) {
current = array[i];
position = less[current];
if (currentPositions[current] === undefined) {
currentPositions[current] = position;
}
result[currentPositions[current]] = current;
currentPositions[current] += 1;
}
return result;
}
/**
* Counting sort algorithm. It's correct only
* for array of integers.<br><br>
* Time complexity: O(N).
*
* @example
* var sort = require('path-to-algorithms/src/' +
* 'sorting/countingsort').countingSort;
* console.log(sort([2, 5, 1, 3, 4])); // [ 1, 2, 3, 4, 5 ]
*
* @public
* @module sorting/countingsort
* @param {Array} array Array which should be sorted.
* @return {Array} Sorted array.
*/
return function (array) {
var less = getLessCount(getCount(array));
return sort(array, less);
};
}());
exports.countingSort = countingSort;
})(typeof window === 'undefined' ? module.exports : window);