§ 18. Сортировка одномерного массива
18.3. Сортировка обменом
|
Рассмотрим еще один метод сортировки, который называется сортировка обменом. Название метода определяется тем, что алгоритм основывается на обмене местами двух элементов массива. Меняются местами те два соседних элемента в массиве, которые стоят «не в порядке». Рассмотрим его на примере того же массива a = {9, 6, 0, 2, 7, 3, 1, 5} (пример 18.6). Цветом выделен тот элемент, правее которого просматривать массив нет необходимости, поскольку элементы, стоящие там, уже отсортированы. Формальное описание алгоритма. На i-м шаге (i = 1, …, n – 1) выполняем: 1. Сравниваем первые два элемента. Если первый больше второго, то меняем их местами. 2. Затем сравниваем второй и третий, третий и четвертый, ..., i и i + 1, при необходимости меняя их местами. 3. После первого шага самый большой элемент массива перемещается на последнее место. Массив будет отсортирован после просмотра, в котором участвуют только первый и второй элементы. Фрагмент программы, содержащий алгоритм сортировки обменом, приведен в примере 18.7. Число сравнений в данном алгоритме, как и в алгоритме сортировки выбором, равно При каждом сравнении возможна перестановка двух элементов в массиве. Поэтому количество перестановок (в худшем случае) будет равно количеству сравнений, т. е. порядка n2 операций. На последних двух проходах в примере 18.6 массив не менялся. Заметим, что если на каком-то шаге алгоритма элементы массива уже упорядочены, то при последующих проходах по массиву перестановки больше выполняться не будут. Следовательно, как только количество выполненных на последнем проходе перестановок станет равным 0, то алгоритм можно заканчивать (пример 18.8). Если проанализировать сортировку обменом, то можно заметить, что самое маленькое число занимает свое место за один проход по массиву, а самое большое перемещается по направлению к своему месту на одну позицию при каждом проходе. Это наводит на мысль чередовать направление проходов. Такая сортировка называется шейкер-сортировкой (шейкерная сортировка, сортировка перемешиванием, коктейльная сортировка). Рассмотрим ее работу на том же массиве а = {9, 6 0, 2, 7, 3, 1, 5} (примеры 18.9, 18.10). Все эти улучшения сокращают количество операций сравнения для частных случаев, однако при неблагоприятной начальной расстановке элементов массива (подумайте, какой именно?) приходится проделать порядка n2 операций сравнения и перестановок. Кроме того, такие модификации усложняют код программы. |
Пример 18.6. Сортировка массива методом обмена:
Алгоритм сортировки обменом часто называют «пузырьковой сортировкой» или сортировкой «методом пузырька» (BubbleSort). Название метода происходит из следующего: на каждом шаге самый «легкий» элемент поднимается до своего места («всплывает»). Для этого нужно просматривать элементы снизу вверх (с конца массива). Берем пару соседних элементов и, в случае если они стоят «не в порядке», меняем их местами. Первый проход по массиву:
Вместо поднятия самого «легкого» элемента можно «топить» самый «тяжелый». В этом случае элементы просматриваются сначала (как в примере 18.6). Пример 18.7. Фрагмент программы сортировки методом обмена. Ввод и вывод такой, как в примере 18.5.
Тестирование.
Пример 18.8. Фрагмент программы сортировки методом обмена с остановкой после того, когда обмены больше не происходят.
В приведенном фрагменте переменная p логического типа используется для определения, были перестановки или нет, а переменная k — для хранения индекса последнего обмена. Переменная r является границей, на которой заканчивается просмотр. Пример 18.9. Сортировка массива шейкерной сортировкой (l — левая граница просмотра, r — правая):
Пример 18.10. Фрагмент программы шейкер-сортировки.
|
