Dyzzet|
C++ Data Science Алгоритмы Темы · Блог · YouTube
Сортировка Шелла
Интерактивная анимация

Сортировка Шелла — обобщение сортировки вставками, поэтому сперва нужно разобраться с ней.

Скажем, что сперва шаг сортировки равен 5 (на практике это число должно быть другим). Получается пять цветных массивов, которые сортируются по отдельности. Как? С помощью сортировки вставками. До и после:

Затем заново разбиваем массив с шагом 3. Сортируем каждый из цветных массивов точно так же — по отдельности, с помощью сортировки вставками.

И наконец задаём шаг, равный 1. Присмотритесь и вы увидите, что если подставить step = 1 и start = 0 в два внутренних цикла, то получится самая обычная сортировка вставками (кстати, на практике циклы можно организовать иначе). В анимации этот шаг специально выглядит так же (с чёрной раскраской и серой), как и для сортировки вставками.

Переменная start обозначает номер самого левого элемента определённого цвета.

function shellSort(data[], size)
{
for (step = 5; step > 0; step -= 2)
{
for (start = 0; start < step; ++start)
{
for (i = step + start; i < size; i += step)
{
for (j = i - step;
j >= 0 and data[j] > data[j + step];
j -= step)
{
swap(data[j], data[j + step]);
}
}
}
}
}

Шаг → Перезапуск Перезапуск (худший случай)

8 ноября 2017
Зарегистрируйтесь и войдите, чтобы оставлять комментарии и голосовать.

Сортировки
Сортировка пузырьком
Сортировка выбором
Гномья сортировка
Сортировка вставками
Сортировка Шелла
Быстрая сортировка
Быстрая сортировка. Вариант с указателем
Пирамидальная сортировка
Также может быть интересным
© MMXI—MMXXIII. RSS. Поддержать сайт
Светлая тема / тёмная тема