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

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

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

При Н = 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.

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

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