Метод простых вставок (метод прямого включения)
Суть метода заключается в том, что из сортируемой последовательности выбирается и анализируется каждый элемент, который помещается «на свое место» в уже отсортированной части последовательности. Принято считать, что элементы, расположенные слева от проверяемого элемента отсортированы в нужном порядке (однако окончательной позиции на промежуточных итерациях эти элементы еще не занимают так как могут быт передвинуты при вставке других элементов). Окончательные позиции элементы займут после проверки всех элементов последовательности.
Данный метод очень прост, однако его нельзя считать эффективным.
Пример сортировки методом простых вставок массива 
( 
) приведен на рисунке 5.1.
| Итерация i | Результат сортировки | |||||||
| 1 | 40 | 
| 8 | 38 | 112 | 10 | 3 | 83 |
| 2 | 40 | 61 | 
| 38 | 112 | 10 | 3 | 83 |
| 3 | 8 | 40 | 61 | 
| 112 | 10 | 3 | 83 |
| 4 | 8 | 38 | 40 | 61 | 
| 10 | 3 | 83 |
| 5 | 8 | 38 | 40 | 61 | 112 | 
| 3 | 83 |
| 6 | 8 | 10 | 38 | 40 | 61 | 112 | 
| 83 |
| 7 | 3 | 8 | 10 | 38 | 40 | 61 | 112 | 
|
| Итог: | 3 | 8 | 10 | 38 | 40 | 61 | 83 | 112 |
Рис. 5.1. Пример сортировки методом простых вставок
– текущий проверяемый элемент;
– место вставки элемента;
| – правая граница отсортированного массива
Метод бинарных (двоичных) включений
Метод бинарных вставок является улучшенным вариантом метода простых вставок. Улучшение базируется на факте, что расположенные в правой части элементы массива упорядочены и заключается в использовании метода бинарного поиска (см. раздел 2.5.1) для определения места вставки последующего элемента.
|
|
|
Пример сортировки методом бинарных вставок массива ( ) приведен на рисунке 5.2.
| Итерация i | Результат сортировки | |||||||
| 1 | 40 |
| 8 | 38 | 112 | 10 | 3 | 83 |
|
| ||||||||
| 2 | 40 | 61 |
| 38 | 112 | 10 | 3 | 83 |
| 3 | 8 | 40 | 61 |
| 112 | 10 | 3 | 83 |
| 4 | 8 | 38 | 40 | 61 |
| 10 | 3 | 83 |
| 5 | 8 | 38 | 40 | 61 | 112 |
| 3 | 83 |
| 6 | 8 | 10 | 38 | 40 | 61 | 112 |
| 83 |
| 7 | 3 | 8 | 10 | 38 | 40 | 61 | 112 |
|
| Итог: | 3 | 8 | 10 | 38 | 40 | 61 | 83 | 112 |
Рис. 5.2. Пример сортировки методом бинарных вставок
– текущий проверяемый элемент;
– место вставки элемента;
| – правая граница отсортированного массива
Сортировка методом Шелла
Сортировка методом Шелла представляет собой модификацию метода простых вставок. Повышение эффективности метода достигается за счет дополнительной возможности обмена местами элементов, расположенных на отдаленных позициях. Суть метода заключается в следующем: на каждой итерации сравниваются и сортируется между собой элементы, расположенные на некотором расстоянии d друг от друга. На каждой последующей итерации значение d уменьшается. На последнем шаге 
, что соответствует методу обычной сортировки вставками.
|
|
|
Одним из важных моментов сортировки является выбор начального и промежуточных значений параметра d. Существует множество подходов к их определению. Автором метода, изобретателем Дональдом Шеллом, предложена следующая последовательность длин расстояний:
(5.1)
Здесь значение первого расстояния определяется как половина числа элементов исходного массива; на каждой последующей итерации это расстояние делится пополам, пока не будет постигнуто значение 1. В худшем случае сложность алгоритма составит 
.
Альтернативный вариант предложен Хиббардом. Здесь расстояние d на каждой итерации определяется в виде последовательности чисел, определяемых по формуле 
, 
. Такая последовательность приводит к сложности 
.
Пример сортировки массива ( ) методом Шелла приведен на рисунке 5.2. Расстояния d рассчитаны согласно выражению (5.1) и представляют собой последовательность 
.
| Итерация i 1 | Результат сортировки
| |||||||
| 40 40 | 61 10 | 8 3 | 38 38 | 112 112 | 10 61 | 3 8 | 83 83 |
2
| 40 3 | 10 10 | 3 8 | 38 38 | 112 49 | 61 61 | 8 112 | 83 83 |
| 3
| 3 | 10 | 8 | 38 | 49 | 61 | 112 | 83 |
| Итог: | 3 | 8 | 10 | 38 | 40 | 61 | 83 | 112 |
|
|
|
Рис. 5.2. Пример сортировки методом Шелла
На рисунке одним цветом выделены элементы, сортируемые в рамках одной итерации. На первой итерации сортируются подсписки, состоящие из 2 элементов: 
, 
, 
, 
. На второй итерации сортируются списки 
и 
. На последней, третьей итерации, методом простых вставок сортируется весь массив 
.
Принято считать, что в определенных случаях при сортировке методом Шелла элементы быстрее «встают на свои места», чем в более простых методах сортировки.
Обменная сортировка
Эта группа методов сортировки подразумевает систематический обмен местами пар элементов, для которых имеется нарушение их упорядоченности. Сортировка прекращается тогда, когда таких пар элементов не остается в последовательности.
Дата добавления: 2020-01-07; просмотров: 356; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!