Сортировка Шелла

Интерактивная анимация

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

Скажем, что сперва шаг сортировки равен 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 · программирование · сортировки