Алгоритм Шелла, названный по имени его создателя Дональда Л. Шелла (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. Исходная последователь-
ность разбивается на следующие четыре части
