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

Сортировка Шелла – это улучшенный метод сортировки вставками. Был предложен Д.Л. Шеллом в 1959 г. Рассмотрим этот метод на примере.

Пример:

Первичный массив ключей	X1	X2	X3	X4	X5	X6	X7
Просмотр 1 Шаг 5 Проходов 5
Просмотр 2 Шаг 3 Проходов 3
Просмотр 3 Шаг 1 Проходов 1
Отсортированный массив ключей

При первом просмотре группируются и сортируются элементы, отстоящие друг от друга на 5 позиций: (Х₁,Х₆), (Х_2,Х₇), (Х₃), (Х₄), (Х₅); при втором проходе — элементы, отстоящие друг от друга на три позиции: (Х₁,Х_4,Х₇), (Х_2,Х₅), (Х_3,Х₆); при третьем — на 1 позицию.

Поскольку первый в сортировке Шелла используемый шаг является большим, отдельные подмассивы достаточно малы по отношению к исходному. Таким образом, сортировка включением над этими подмассивами работает достаточно быстро – O(N²) (эффективно при малом N). Сортировка каждого подмассива приводит к тому, что весь массив становиться ближе к отсортированному виду, что также делает эффективным использование сортировки включением. Так как массив становится более упорядоченным, то O(N) < порядок ФBC <O(N²).

Если некоторый массив частично отсортирован с использованием шага k, а затем сортируется частично с использованием шага j, то данный массив остается частично отсортированным по шагу k, т.е. последующие частичные сортировки не нарушают результата предыдущих сортировок. Следующий шаг отличается от предыдущего следующим образом: h_t=1, h_i+1<h_i.