2020-11-25 21:10:50 +02:00
|
|
|
/*
|
2020-11-25 21:13:41 +02:00
|
|
|
https://en.wikipedia.org/wiki/Pigeonhole_sort
|
|
|
|
|
|
2020-11-25 21:10:50 +02:00
|
|
|
*Pigeonhole sorting is a sorting algorithm that is suitable
|
|
|
|
|
* for sorting lists of elements where the number of elements
|
|
|
|
|
* (n) and the length of the range of possible key values (N)
|
|
|
|
|
* are approximately the same.
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
export function pigeonHoleSort(arr) {
|
2020-11-25 21:31:27 +02:00
|
|
|
let min = arr[0]
|
|
|
|
|
let max = arr[0]
|
2020-11-25 21:10:50 +02:00
|
|
|
|
2020-11-25 21:31:27 +02:00
|
|
|
for (let i = 0; i < arr.length; i++) {
|
2023-10-03 23:08:19 +02:00
|
|
|
if (arr[i] > max) {
|
|
|
|
|
max = arr[i]
|
|
|
|
|
}
|
|
|
|
|
if (arr[i] < min) {
|
|
|
|
|
min = arr[i]
|
|
|
|
|
}
|
2020-11-25 21:31:27 +02:00
|
|
|
}
|
2020-11-25 21:10:50 +02:00
|
|
|
|
2020-11-25 21:31:27 +02:00
|
|
|
const range = max - min + 1
|
|
|
|
|
const pigeonhole = Array(range).fill(0)
|
2020-11-25 21:10:50 +02:00
|
|
|
|
2020-11-25 21:31:27 +02:00
|
|
|
for (let i = 0; i < arr.length; i++) {
|
|
|
|
|
pigeonhole[arr[i] - min]++
|
|
|
|
|
}
|
2020-11-25 21:10:50 +02:00
|
|
|
|
2020-11-25 21:31:27 +02:00
|
|
|
let index = 0
|
2020-11-25 21:10:50 +02:00
|
|
|
|
2020-11-25 21:31:27 +02:00
|
|
|
for (let j = 0; j < range; j++) {
|
|
|
|
|
while (pigeonhole[j]-- > 0) {
|
|
|
|
|
arr[index++] = j + min
|
2020-11-25 21:10:50 +02:00
|
|
|
}
|
2020-11-25 21:31:27 +02:00
|
|
|
}
|
2022-04-01 12:28:43 +05:30
|
|
|
return arr
|
2020-11-25 21:10:50 +02:00
|
|
|
}
|
