2021-01-24 23:33:15 +05:30
|
|
|
/**
|
2021-01-24 23:34:56 +05:30
|
|
|
* Counting sort is an algorithm for sorting a collection
|
2021-01-24 23:33:15 +05:30
|
|
|
* of objects according to keys that are small integers.
|
2021-01-24 23:34:56 +05:30
|
|
|
*
|
2021-01-24 23:33:15 +05:30
|
|
|
* It is an integer sorting algorithm.
|
2021-01-24 23:34:56 +05:30
|
|
|
*
|
2021-01-24 23:33:15 +05:30
|
|
|
* Wikipedia: https://en.wikipedia.org/wiki/Counting_sort
|
|
|
|
|
* Animated Visual: https://www.cs.usfca.edu/~galles/visualization/CountingSort.html
|
2018-10-14 00:01:35 +03:00
|
|
|
*/
|
|
|
|
|
|
2021-10-11 12:29:03 +02:00
|
|
|
export const countingSort = (arr, min, max) => {
|
2021-08-06 22:54:48 +05:30
|
|
|
// Create an auxiliary resultant array
|
|
|
|
|
const res = []
|
2021-08-08 17:21:05 +05:30
|
|
|
// Create and initialize the frequency[count] array
|
|
|
|
|
const count = new Array(max - min + 1).fill(0)
|
2021-08-06 22:54:48 +05:30
|
|
|
// Populate the freq array
|
|
|
|
|
for (let i = 0; i < arr.length; i++) {
|
2021-08-08 17:21:05 +05:30
|
|
|
count[arr[i] - min]++
|
2018-10-14 00:01:35 +03:00
|
|
|
}
|
2021-08-08 17:21:05 +05:30
|
|
|
// Create a prefix sum array out of the frequency[count] array
|
2021-08-06 22:54:48 +05:30
|
|
|
count[0] -= 1
|
|
|
|
|
for (let i = 1; i < count.length; i++) {
|
|
|
|
|
count[i] += count[i - 1]
|
2018-10-14 00:01:35 +03:00
|
|
|
}
|
2021-08-06 22:54:48 +05:30
|
|
|
// Populate the result array using the prefix sum array
|
|
|
|
|
for (let i = arr.length - 1; i >= 0; i--) {
|
|
|
|
|
res[count[arr[i] - min]] = arr[i]
|
|
|
|
|
count[arr[i] - min]--
|
|
|
|
|
}
|
2021-08-08 17:14:41 +05:30
|
|
|
return res
|
2018-10-14 00:01:35 +03:00
|
|
|
}
|
|
|
|
|
|
2021-01-24 23:34:22 +05:30
|
|
|
/**
|
2021-08-06 22:54:48 +05:30
|
|
|
* Implementation of Counting Sort
|
|
|
|
|
*/
|
2021-10-11 12:29:03 +02:00
|
|
|
// const array = [3, 0, 2, 5, 4, 1]
|
|
|
|
|
// countingSort(array, 0, 5)
|
