Структурограмма метода Шелла с сортировкой вставкой отдельных
частей приведена на рис.
При Н = 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. Среднее число перестановок - 
