2021-02-01 20:59:59 +05:30
|
|
|
/**
|
2021-02-01 21:02:15 +05:30
|
|
|
* Flashsort is a distribution sorting algorithm showing linear
|
2021-02-01 20:59:59 +05:30
|
|
|
* computational complexity O(n) for uniformly distributed
|
2018-10-14 00:16:51 +03:00
|
|
|
* data sets and relatively little additional memory requirement.
|
2021-02-01 21:02:15 +05:30
|
|
|
*
|
2021-02-01 20:59:59 +05:30
|
|
|
* Wikipedia: https://en.wikipedia.org/wiki/Flashsort
|
2018-10-14 00:16:51 +03:00
|
|
|
*/
|
|
|
|
|
|
2021-10-11 12:29:03 +02:00
|
|
|
export function flashSort (arr) {
|
2020-05-03 09:05:12 +02:00
|
|
|
let max = 0; let min = arr[0]
|
|
|
|
|
const n = arr.length
|
|
|
|
|
const m = ~~(0.45 * n)
|
|
|
|
|
const l = new Array(m)
|
|
|
|
|
|
2018-10-14 00:16:51 +03:00
|
|
|
for (let i = 1; i < n; ++i) {
|
|
|
|
|
if (arr[i] < min) {
|
2020-05-03 09:05:12 +02:00
|
|
|
min = arr[i]
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
|
|
|
|
if (arr[i] > arr[max]) {
|
2020-05-03 09:05:12 +02:00
|
|
|
max = i
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
|
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
|
2018-10-14 00:16:51 +03:00
|
|
|
if (min === arr[max]) {
|
2020-05-03 09:05:12 +02:00
|
|
|
return arr
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
|
|
|
|
|
const c1 = (m - 1) / (arr[max] - min)
|
|
|
|
|
|
2018-10-14 00:16:51 +03:00
|
|
|
for (let k = 0; k < m; k++) {
|
2020-05-03 09:05:12 +02:00
|
|
|
l[k] = 0
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
|
2018-10-14 00:16:51 +03:00
|
|
|
for (let j = 0; j < n; ++j) {
|
2020-05-03 09:05:12 +02:00
|
|
|
const k = ~~(c1 * (arr[j] - min))
|
|
|
|
|
++l[k]
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
|
2018-10-14 00:16:51 +03:00
|
|
|
for (let p = 1; p < m; ++p) {
|
2020-05-03 09:05:12 +02:00
|
|
|
l[p] = l[p] + l[p - 1]
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
|
|
|
|
|
let hold = arr[max]
|
|
|
|
|
arr[max] = arr[0]
|
|
|
|
|
arr[0] = hold
|
|
|
|
|
|
2018-10-14 00:16:51 +03:00
|
|
|
// permutation
|
2020-05-03 09:05:12 +02:00
|
|
|
let move = 0; let t; let flash
|
|
|
|
|
let j = 0
|
|
|
|
|
let k = m - 1
|
|
|
|
|
|
2018-10-14 00:16:51 +03:00
|
|
|
while (move < (n - 1)) {
|
|
|
|
|
while (j > (l[k] - 1)) {
|
2020-05-03 09:05:12 +02:00
|
|
|
++j
|
|
|
|
|
k = ~~(c1 * (arr[j] - min))
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
if (k < 0) break
|
|
|
|
|
flash = arr[j]
|
2018-10-14 00:16:51 +03:00
|
|
|
while (j !== l[k]) {
|
2020-05-03 09:05:12 +02:00
|
|
|
k = ~~(c1 * (flash - min))
|
|
|
|
|
hold = arr[t = --l[k]]
|
|
|
|
|
arr[t] = flash
|
|
|
|
|
flash = hold
|
|
|
|
|
++move
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
|
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
|
2018-10-14 00:16:51 +03:00
|
|
|
// insertion
|
|
|
|
|
for (j = 1; j < n; j++) {
|
2020-05-03 09:05:12 +02:00
|
|
|
hold = arr[j]
|
|
|
|
|
let i = j - 1
|
2018-10-14 00:16:51 +03:00
|
|
|
while (i >= 0 && arr[i] > hold) {
|
2020-05-03 09:05:12 +02:00
|
|
|
arr[i + 1] = arr[i--]
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
arr[i + 1] = hold
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
return arr
|
2018-10-14 00:16:51 +03:00
|
|
|
}
|
|
|
|
|
|
2021-02-01 21:01:00 +05:30
|
|
|
/**
|
|
|
|
|
* Implementation of Flash Sort
|
|
|
|
|
*/
|
2021-10-11 12:29:03 +02:00
|
|
|
// const array = [3, 0, 2, 5, -1, 4, 1, -2]
|
|
|
|
|
// flashSort(array)
|
