Эффективность алгоритма сортировки шелла

Блок-схема сортировки шелла

Пример работы сортировки шелла

Необходимо отсортировать массив: 9, 74, 62, 5, 81, 3, 14, 15, 44, 30, 16, 7, 22, 41, 56, 25, 1, 90. Всего в массиве 18 элементов.

Произведём необходимые вычисления по формулам (14.5) и (14.6):

T=trunс(ln18/ln2)-1=4-1=3; k= 2^t-1=2³-1=8-1=7.

Тогда из второй последовательности расстояний, предложенной д. Кнутом, выбираем количество шагов t=3, которые равны: 7, 3 и 1.

Сначала будем выбирать подпоследовательности, где шаг между элементами равен 7. Таких подпоследовательностей так же будет семь. Первый элемент такой первой последовательности – это 9, а первый элемент второй последовательности – это 74, тогда как первый элемент третьей последовательности – 62, и т.д. К каждой такой подпоследовательности применяем метод прямого включения (табл. 14.1).

Потом выбираем три подпоследовательности, где шаг между элементами равен 3, и их сортируем методом прямого включения (табл. 14.2).

А далее сортируется и весь массив прямым включением, так как шаг уже равен единице (табл. 14.3).

Таблица 14.1

Выбор семи последовательностей с шагом равным 7 между элементами и их сортировка прямой вставкой

Таблица 14.2

Выбор трех последовательностей с шагом равным 3 между элементами и их сортировка прямой вставкой

Таблица 14.3

Выбор трех последовательностей с шагом равным 3 между элементами и их сортировка прямой вставкой

В блок-схеме алгоритма сортировки шелла (рис. 14.1) используется алгоритм прямого включения для сортировки подпоследовательностей, где расстояния между элементами равно k (рис. 14.2).

Известно, что алгоритм шелла имеет сложность примерно n^3/2. Данное значение чуть хуже, чем заявленное значение n*logn. Но, не смотря на это, данная сортировка относится к улучшенным сортировкам.