Сортировка расческой, JavaScript.
Сортировка расческой (Comb sort) представляет собой еще один улучшенный вариант сортировки пузырьком. Но в отличие от нее этот алгоритм больше не является устойчивой сортировкой.
Сортировка пузырьком основана на сравнении и перестановке соседних элементов, то есть разница их индексов всегда равна 1. Но если увеличить ее и сравнивать элементы стоящие на большем расстоянии друг от друга, то минимальные элементы, находящиеся в конце массива, можно передвинуть в его начало за меньшее количество перестановок (мы рассматриваем сортировку по возрастанию).
На каком же расстоянии стоит сравнивать элементы?
Во первых, это число зависит от длины самого массива — чем больше массив, тем больший разрыв можно брать между элементами.
Во вторых, это расстояние должно постепенно уменьшиться до 1, чтобы на последней итерации цикла мы смогли проверить все элементы один за другим как в обычной сортировке пузырьком.
Это хорошо видно на иллюстрации:
Число, на которое должен раз за разом уменьшаться разрыв, было названо фактором уменьшения и выведено авторами сортировки из формулы:
( 1 / ( 1-e^(-φ) ) = 1.247330950103979,
где е — экспонента; φ — “золотое” число.
Нам достаточно округлить его до 1.247, и вывести первое значение нашего расстояния, равное длине массива, деленной на фактор уменьшения, и округленного до ближайшего целого. Затем после каждой итерации мы будет его снова делить на фактор, округлять, и так пока оно не станет равным 1.
Код алгоритма на js будет выглядеть следующим образом:
const combSort = arr => {
const l = arr.length;
const factor = 1.247;
let gapFactor = l / factor; while (gapFactor > 1) {
const gap = Math.round(gapFactor); for (let i = 0, j = gap; j < l; i++, j++) {
if (arr[i] > arr[j]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
} gapFactor = gapFactor / factor;
} return arr;
};
Также его работа хорошо продемонстрирована на этом видео:
Надеюсь у вас не осталось вопросов :)
Но если остались — добро пожаловать в комментарии.
P. S. Все мы люди :) А значит нам свойственно ошибаться.
Увидели опечатку или ошибку — выделите текст, кликните в сплывающем меню иконку сообщения с замочком и напишите о ней.
Я буду вам очень признательна.
