Пример работы сортировки шелла
Необходимо отсортировать массив: 9, 74, 62, 5, 81, 3, 14, 15, 44, 30, 16, 7, 22, 41, 56, 25, 1, 90. Всего в массиве 18 элементов.
Произведём необходимые вычисления по формулам (14.5) и (14.6):
T=trunс(ln18/ln2)-1=4-1=3; k= 2t-1=23-1=8-1=7.
Тогда из второй последовательности расстояний, предложенной д. Кнутом, выбираем количество шагов t=3, которые равны: 7, 3 и 1.
Сначала будем выбирать подпоследовательности, где шаг между элементами равен 7. Таких подпоследовательностей так же будет семь. Первый элемент такой первой последовательности – это 9, а первый элемент второй последовательности – это 74, тогда как первый элемент третьей последовательности – 62, и т.д. К каждой такой подпоследовательности применяем метод прямого включения (табл. 14.1).
Потом выбираем три подпоследовательности, где шаг между элементами равен 3, и их сортируем методом прямого включения (табл. 14.2).
А далее сортируется и весь массив прямым включением, так как шаг уже равен единице (табл. 14.3).
Таблица 14.1
Выбор семи последовательностей с шагом равным 7 между элементами и их сортировка прямой вставкой
№ |
Массив, подпоследовательности |
Перестановка |
|
9, 74, 62, 5, 81, 3, 14, 15, 44, 30, 16, 7, 22, 41, 56, 25, 1, 90 |
|
1 |
9 15 56 |
Нет |
2 |
74 44 25 |
Да |
|
44 74 25 |
Да |
|
25 44 74 |
Нет |
3 |
62 30 1 |
Да |
|
30 62 1 |
Да |
|
1 30 62 |
Нет |
4 |
5 16 90 |
Нет |
5 |
81 7 |
Да |
|
7 81 |
Нет |
6 |
3 22 |
Нет |
7 |
14 41 |
Нет |
|
9, 25, 1, 5, 7, 3, 14, 15, 44, 30, 16,81, 22, 41, 56, 74,62, 90 |
Готово |
Таблица 14.2
Выбор трех последовательностей с шагом равным 3 между элементами и их сортировка прямой вставкой
№ |
Массив, подпоследовательности |
Перестановка |
|
9, 25, 1, 5, 7, 3, 14, 15, 44, 30, 16,81, 22, 41, 56, 74,62, 90 |
|
1 |
9 5 14 30 22 74 |
Да |
|
5 9 14 30 22 74 |
Да |
|
5 9 14 22 30 74 |
Нет |
2 |
25 7 15 16 41 62 |
Да |
|
7 25 15 16 41 62 |
Да |
|
7 15 25 16 41 62 |
Да |
|
7 15 16 25 41 62 |
Нет |
3 |
1 3 44 81 56 90 |
Да |
|
1 3 44 56 81 90 |
Нет |
|
5, 7, 1, 9, 15, 3, 14, 16,44, 22, 25,56, 30, 41, 81, 74,62, 90 |
Готово |
Таблица 14.3
Выбор трех последовательностей с шагом равным 3 между элементами и их сортировка прямой вставкой
№ |
Массив, подпоследовательности |
Перестановка |
|
5, 7, 1, 9, 15, 3, 14, 16, 44, 22, 25, 56, 30, 41, 81, 74, 62, 90 |
|
1 |
5, 7, 1, 9, 15, 3, 14, 16, 44, 22, 25, 56, 30, 41, 81, 74, 62, 90 |
Да |
|
1, 5, 7, 9, 15, 3, 14, 16, 44, 22, 25, 56, 30, 41, 81, 74, 62, 90 |
Да |
|
1, 3, 5, 7, 9, 15, 14, 16, 44, 22, 25, 56, 30, 41, 81, 74, 62, 90 |
Да |
|
1, 3, 5, 7, 9, 14, 15, 16, 44, 22, 25, 56, 30, 41, 81, 74, 62, 90 |
Да |
|
1, 3, 5, 7, 9, 14, 15, 16, 22, 44, 25, 56, 30, 41, 81, 74, 62, 90 |
Да |
|
1, 3, 5, 7, 9, 14, 15, 16, 22, 25, 44, 56, 30, 41, 81, 74, 62, 90 |
Да |
|
1, 3, 5, 7, 9, 14, 15, 16, 22, 25, 30, 44, 56, 41, 81, 74, 62, 90 |
Да |
|
1, 3, 5, 7, 9, 14, 15, 16, 22, 25, 30, 41, 44, 56, 81, 74, 62, 90 |
Да |
|
1, 3, 5, 7, 9, 14, 15, 16, 22, 25, 30, 41, 44, 56, 74, 81, 62, 90 |
Да |
|
1, 3, 5, 7, 9, 14, 15, 16, 22, 25, 30, 41, 44, 56, 62, 74, 81, 90 |
Готово |
Блок-схема сортировки шелла
В блок-схеме алгоритма сортировки шелла (рис. 14.1) используется алгоритм прямого включения для сортировки подпоследовательностей, где расстояния между элементами равно k (рис. 14.2).
Эффективность алгоритма сортировки шелла
Известно, что алгоритм шелла имеет сложность примерно n3/2. Данное значение чуть хуже, чем заявленное значение n*logn. Но, не смотря на это, данная сортировка относится к улучшенным сортировкам.
Улучшенные методы сортировки. Пирамидальная сортировка.
Её эффективность.
Пирамидальная сортировка
Пирамидальная сортировка – это улучшенный алгоритм сортировки простым выбором. Данное улучшение было разработано р.флойдом. Он предложил перестраивать линейный массив в пирамиду, которая моделирует бинарное дерево. В таком дереве два нижних соседних элемента всегда имеют один элемент, который расположен над ними на уровень выше (рис. 15.1). Минимальный элемент ищется среди этих двух соседних элементов.
Все элементы линейного массива можно распределить последовательно, начиная с первого элемента и кончая последним элементом, используя определённый принцип расположения элементов (рис. 15.1). Само действие «распределить последовательно» означает, что элементы данного массива будут выбираться в определённом заданном порядке, так что бы виртуально моделировалась заданная конструкция.
A[1] |
|||||||
A[2] |
A[3] |
||||||
A[4] |
A[5] |
A[6] |
A[7] |
||||
A[8] |
A[9] |
A[10] |
A[11] |
A[12] |
A[13] |
A[14] |
A[15] |
Рисунок 15.1 принцип расположения элементов массива в пирамиде