Метод Шелла (сортировка с убывающим шагом)

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

 

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

Структурограмма метода Шелла с сортировкой вставкой отдельных

частей приведена на рис.

 

 

При Н = 1 – обычная вставка

 

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

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

12 5 4 3 1 9 8 6 7

 

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

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

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

12 1 7 5 9 4 8 3 6.

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

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

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

1 5 4 3 7 9 8 6 12.

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

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

на 2 элемента

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

1 4 7 8 12 5 3 9 6.

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

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

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

1 3 4 5 7 6 8 9 12.

Затем снова H сокращается вдвое и становится равным 1. При

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

После этого :

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

1 3 4 5 6 7 8 9 12.

 

Характеристики метода Шелла.

1. Каждый просмотр частично сортирует набор данных.

2. Сортировка высокоэффективна за счет наличия частично отсортиро-

ванных записей. Наиболее эффективен для N>100.

2. Среднее число сравнений – .

3. Среднее число перестановок -