Как работает сортировка расчёской

Как работает сортировка расчёской

Улучшаем пузырьковую сортировку.

Продолжаем рассказывать о разных видах алгоритмов сортировок. Мы уже разобрали самую простую пузырьковую сортировку и теперь улучшаем её — пишем сортировку расчёской.

Коротко про пузырьковую сортировку

Самый простой способ сортировки, который работает по такому принципу: берутся два элемента, сравниваются между собой и сразу меняются местами, если второй больше первого. Называется так потому, что это похоже на пузырьки воздуха в воде, которые всплывают наверх.

Если представить числа в виде столбиков, в зависимости от их размера, то пузырьковая сортировка будет выглядеть так:

Как работает сортировка расчёской

Чем плоха пузырьковая сортировка

Главный недостаток пузырьковой сортировки — её скорость и полный перебор всех элементов массива. Скорость работы алгоритма зависит не от количества сравнений (они выполняются быстро), а от количества перестановок (на них как раз и тратится много процессорного времени).

Получается, что если у нас в массиве в начале будет много больших элементов, которые нужно отправить в конец массива, то каждый раз нам придётся менять их местами с соседями, по одной перестановке за раз. Можно представить, что мы несем куда-то не слишком тяжёлый ящик, но после каждого шага ставим этот ящик на пол, потом поднимаем, делаем шаг, снова ставим, снова поднимаем. Процедуры простые, но из-за устройства алгоритма мы делаем эти процедуры слишком много раз. 

В чём хитрость сортировки расчёской

Раз у нас большие элементы могут тормозить весь процесс, то можно их перекидывать не на соседнее место, а подальше. Так мы уменьшим количество перестановок, а с ними сэкономим и процессорное время, нужное на их обработку.

Но отправлять каждый большой элемент сразу в конец массива будет недальновидно — мы же не знаем, насколько этот элемент большой по сравнению с остальными элементами. Поэтому в сортировке расчёской сравниваются элементы, которые отстоят друг от друга на каком-то расстоянии. Оно не слишком большое, чтобы сильно не откидывать элементы и возвращать потом большинство назад, но и не слишком маленькое, чтобы можно было отправлять не на соседнее место, а чуть дальше.

👉 Опытным путём программисты установили оптимальное расстояние между элементами — это длина массива, поделённая на 1,247 (понятное дело, расстояние нужно округлить до целого числа). С этим числом алгоритм работает быстрее всего.

Как работает алгоритм сортировки расчёской

На первом шаге мы находим длину массива (например, 10 элементов) и делим её на 1,247. Допустим, после округления у нас получилось число 8. Теперь мы проходим первый цикл пузырьковой сортировки, только сравнивая не 1 и 2, 2 и 3, а сразу 1 и 8, 2 и 9, 3 и 10. Это отправит самые большие числа, если они есть в начале, в самый конец. Всего на первом шаге будет три сравнения.

На втором шаге мы берём число 8 из предыдущего этапа и снова делим его на 1,247, получая число 6. Теперь мы снова проходим весь массив и сравниваем так:

1 и 6


2 и 7


3 и 8


4 и 9


5 и 10

Уже получилось 5 перестановок и снова крупные числа улетели поближе к концу массива.

Так мы уменьшаем размер шага до тех пор, пока он не станет меньше единицы — к этому моменту массив будет полностью отсортирован.

🤔 Сортировка расчёской называется так из-за того, что мы как бы расчёсываем массив сначала широким гребнем (большой шаг), потом гребнем поменьше (шаг поменьше). В конце шаг равен единице, как в пузырьковой сортировке.

Как работает сортировка расчёской

Сортировка расчёской на JavaScript

Запустите этот код в консоли браузера, чтобы посмотреть, как алгоритм шаг за шагом приводит массив в нормальный вид:

// исходный массив 
var arr = [3,14,1,7,9,8,11,6,4,2]

// получаем длину массива
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]];
        }
        // выводим текущее состояние массива в консоль 
        // это необязательный шаг, он здесь для наглядности 
        console.log(arr);
    }
    // в конце цикла рассчитываем новый шаг
    gapFactor = gapFactor / factor;
}

Почему это лучше пузырьковой сортировки, ведь алгоритм выглядит сложнее и в конце мы всё равно сравниваем соседние элементы?

То, что код выглядит сложнее, ничего не значит: нам нужна не оценка сложности кода, а скорость и эффективность работы.

Расчёска лучше пузырьковой сортировки, потому что в ней намного меньше операций перестановки. Именно перестановка занимает основное время процессора. В самом худшем случае алгоритм сортировки расчёской будет работать так же, как и пузырьковая, а в среднем — алгоритм работает быстрее пузырьковой.

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Олег Вешкурцев

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства и компенсация, если вы пойдёте работать в «Яндекс».
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Как работает пузырьковая сортировка
Как работает пузырьковая сортировка

Самый простой, но не самый эффективный алгоритм.

Зачем нужна сортировка в программировании
Зачем нужна сортировка в программировании

И почему это любят спрашивать на собеседовании.

«Программисты, которые умеют писать алгоритмы, — нишевая профессия»
«Программисты, которые умеют писать алгоритмы, — нишевая профессия»

Мнение работодателя Коли Митина.

Flipper Zero: как устроен хакерский тамагочи
Flipper Zero: как устроен хакерский тамагочи

И сколько на нём можно заработать.

10 главных конструкций языка Swift
10 главных конструкций языка Swift

Быстрый гайд по языку.

Знакомимся с вектором
Знакомимся с вектором

Основы линейной алгебры для тех, кого это миновало в универе.

Chrome OS — операционная система из браузера
Chrome OS — операционная система из браузера

Работает быстро, но с множеством ограничений

MySQL — царица баз
MySQL — царица баз

Она сложная, но с ней всё просто.

NFT — новые модные токены. Зачем они нужны и не развод ли это?
NFT — новые модные токены. Зачем они нужны и не развод ли это?

Объясняем на Аллегровой.

Роман Халкечев, руководитель отдела аналитики в Яндекс.Еде и Лавке
Роман Халкечев, руководитель отдела аналитики в Яндекс.Еде и Лавке

Часть 2: о Яндекс.Еде и Лавке, аналитических задачах и оптимизации бизнеса на основе данных.

Как работает сканер отпечатка пальца
Как работает сканер отпечатка пальца

Удобно, но не всегда безопасно.

Что такое рефакторинг
Что такое рефакторинг

Как сделать код чище и понятнее.

Почему Ruby — особенный язык

Потому что он прост как JavaScript и многогранен как С++.

easy