2017-09-30 19:59:06 +02:00
|
|
|
/*
|
|
|
|
|
* Shell Sort sorts an array based on insertion sort algorithm
|
|
|
|
|
* more information: https://en.wikipedia.org/wiki/Shellsort
|
|
|
|
|
*
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
export function shellSort(items) {
|
2021-05-21 11:16:11 +05:30
|
|
|
let interval = 1
|
2020-05-03 09:05:12 +02:00
|
|
|
|
|
|
|
|
while (interval < items.length / 3) {
|
|
|
|
|
interval = interval * 3 + 1
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
while (interval > 0) {
|
2021-05-21 11:16:11 +05:30
|
|
|
for (let outer = interval; outer < items.length; outer++) {
|
|
|
|
|
const value = items[outer]
|
|
|
|
|
let inner = outer
|
2020-05-03 09:05:12 +02:00
|
|
|
|
|
|
|
|
while (inner > interval - 1 && items[inner - interval] >= value) {
|
|
|
|
|
items[inner] = items[inner - interval]
|
|
|
|
|
inner = inner - interval
|
|
|
|
|
}
|
|
|
|
|
items[inner] = value
|
2017-09-30 19:59:06 +02:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
interval = (interval - 1) / 3
|
|
|
|
|
}
|
|
|
|
|
return items
|
2017-09-30 19:59:06 +02:00
|
|
|
}
|
