 |
Шейкерная сортировка
|
|
|
|
Модификацией сортировки стандартным обменом является шейкерная или челночная сортировка. Здесь, как и в методе пузырька, проводится попарное сравнение элементов. При этом первый проход осуществляется слева направо, второй — справа налево и т. д. Иными словами, меняется направление просмотра элементов списка.
Шейкерная сортировка хороша тогда, когда элементы последовательности почти упорядочены.
-------------------------------------------------------------------------------------------------------------------------------------
Исходный массив:
27 412 71 81 59 14 273 87
Шаги сортировки:
14 27 412 71 81 59 87 273
14 27 71 81 59 87 273 412
14 27 59 71 81 87 273 412
14 27 59 71 81 87 273 412
Отсортированный массив
14 27 59 71 81 87 273 412
-------------------------------------------------------------------------------------------------------------------------------------
Сложность метода стандартного обмена — О(п2).
Сортировка Шелла
В методе Шелла сравниваются не соседние элементы, а элементы, расположенные на расстоянии (
) (где 
— шаг между сравниваемыми элементами, [ ] — целая часть от числа). После каждого просмотра шаг уменьшается вдвое. На последнем просмотре он сокращается до 
.
Например, пусть дан список, в котором число элементов четно:
{40, 11, 83, 57, 32, 21, 75, 64}.
Список длины п разбивается на п/2 частей, т. е. 
.
При первом просмотре сравниваются элементы, отстоящие друг от друга на 
(рис. 7), т. е. 
и т. д. Если 
, то происходит обмен между позициями i и i+d. Перед вторым просмотром выбирается шаг 
(рис. 8). Затем выбираем шаг 
(рис. 9), т. е. имеем аналогию с методом стандартного обмена.
Сложность метода Шелла — 
.
| Исходный массив | ||||||||
|
| ||||||||
| Полученный массив |
Рис. 7. Метод Шелла (шаг ()
|
|
|
| Исходный массив | ||||||||
| ||||||||
| Полученный массив |
Рис. 8. Метод Шелла (шаг ()
| Исходный массив | ||||||||
|
| ||||||||
| Полученный массив |
Рис. 9. Метод Шелла (шаг ()
|
|
|
