Метод Шелла

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

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

K(1) K(5) K(9)

12 1 7

K(2) K(6)

5 9

K(3) K(7)

4 8

K(4) K(8)

3 6

После упорядочения элементов внутри каждой последовательности

набор данных будет иметь следующий вид:

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

1 5 4 3 7 9 8 6 12.

Затем шаг J сокращается вдвое и становится равным 2. Образуются

следующие 2 последовательности элементов, отстоящих друг от друга

на 2 элемента

K(1) K(3) K(5) K(7) K(9)

1 4 7 8 12