Метод Шелла

Алгоритм Шелла, названный по имени его создателя Дональда Л. Шелла (Donald L. Shell), намного эффективнее, чем метод пузырьков. Здесь сначала сравниваются отдаленные, а затем – близкорасположенные элементы данных.

Исходный набор данных на каждом просмотре разбивается на части. Части образуются из записей, отстоящих друг от друга на J позиций. Производится сортировка записей внутри этих частей обычными методами (обмен, вставка и др.). После каждого просмотра J сокращается. При этом число частей уменьшается, а их длина увеличивается.

Сортировка заканчивается просмотром с J=1. В методе Шелла первоначально J устанавливается равным INT(N/2), а затем сокращается вдвое.

Переменная J содержит интервал, разделяющий сравниваемые элементы данных. Сначала J равен половине количества элементов. В процессе сортировки J уменьшается на каждом шаге в два раза, пока не начнет выполняться сравнение соседних элементов, как в методе пузырька.

Пример. Исходная последовательность

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)

12 5 4 3 1 9 8 6 7

N=9

Первоначально J принимается равным 4. Исходная последователь-

ность разбивается на следующие четыре части