Светлая тема /
тёмная тема
Сортировка Шелла
Интерактивная анимация
Сортировка Шелла — обобщение сортировки вставками, поэтому сперва нужно разобраться с ней.
Скажем, что сперва шаг сортировки равен 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)
j >= 0 and data[j] > data[j + step];
j -= step)
{
swap(data[j], data[j + step]);
}
}
}
}
}