 |
1.2.1. Сортировка обменом. 1.2.1.1. Метод стандартного обмена. 1.2.1.2. Просеивание ("челночная" сортировка)
|
|
|
|
1. 2. 1. Сортировка обменом
При сортировке методом обмена два определенным образом выбранных элемента, расположение которых не соответствует порядку, меняют местами. Этот процесс повторяется до тех пор, пока остаются такие пары. К обменным относятся следующие сортировки: парный обмен, стандартный обмен (метод " пузырька" ), шейкер-сортировка, метод Бэтчера, " быстрая сортировка", просеивание (" челночная" сортировка) и др. Все эти методы различаются между собой способами просмотра и выбора в сортируемой последовательности элементов для сравнения.
1. 2. 1. 1. Метод стандартного обмена
Этот метод основан на попарном сравнении ключей соседних записей. Если порядок следования записей в очередной паре неправилен, то эти элементы обмениваются местами. При первом просмотре ключ 1-й записи сравнивается с ключом 2-й записи и, если 2-й меньше, то они меняются местами. Затем ключ, расположенный во 2-й позиции, сравнивается с ключом из 3-й позиции. Обмен происходит, если меньший из них находится в 3-й позиции. После этого позиция 3 сравнивается с позицией 4, позиция 4 - с позицией 5 и т. д. Когда позиция N-1 сравнивается с позицией N, просмотр заканчивается. После первого просмотра запись с наибольшим ключом займет N-ю позицию, а минимальный элемент переместится на одну позицию к началу последовательности.
Второй просмотр идентичен первому лишь с той разницей, что он заканчивается после сравнения ключей N-2-й и N-1-й записей.
Так как на каждом из проходов очередные наибольшие элементы занимают соответственно позиции N, N-1, N-2 и т. д., то не более как за N-1 проход исходная последовательность будет упорядочена.
Для ускорения работы алгоритма в процессе сортировки при каждом просмотре регистрируется факт наличия или отсутствия обмена. Просмотр, в результате которого не было произведено ни одного обмена, заканчивает сортировку.
|
|
|
Структурограмма алгоритма сортировки методом стандартного обмена приведена на рис. 1.
Пример. Пусть требуется упорядочить в порядке возрастания значений следующий массив чисел из 8 элементов:
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)
25 57 48 37 12 92 86 33.
На первом просмотре производятся следующие сравнения и обмены (в начале просмотра признаку обмена FLAG присваивается значение, равное 0): К(1) с К(2) (25 с 57) нет обмена
К(2) с К(3) (57 с 48) обмен (FLAG=1)
К(3) с К(4) (57 с 37) обмен
К(4) с К(5) (57 с 12) обмен
К(5) с К(6) (57 с 92) нет обмена
К(6) с К(7) (92 с 86) обмен
К(7) с К(8) (92 с 33) обмен.
Таким образом, после 1-го просмотра элементы массива будут
располагаться в следующем порядке:
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)
25 48 37 12 57 86 33 92,
а признак обмена FLAG=1.
В результате первого просмотра наибольший элемент (в данном случае 92) находится в нужной позиции внутри последовательности, а минимальный элемент (12) перемещается на одну позицию к началу списка.
На втором просмотре производятся следующие сравнения и обмены (первоначально FLAG=0):
К(1) с К(2) (25 с 48) нет обмена
К(2) с К(3) (48 с 37) обмен (FLAG=1)
К(3) с К(4) (48 с 12) обмен
К(4) с К(5) (48 с 57) нет обмена
К(5) с К(6) (57 с 86) нет обмена
К(6) с К(7) (86 с 33) обмен.
После второго просмотра элементы массива будут располагаться в следующей последовательности:
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)
25 37 12 48 57 33 86 92.
Так как признак обмена после второго просмотра равен 1, необходимо дальше продолжать сортировку. В результате последующие просмотры выглядят следующим образом:
просмотр 3 (FLAG=0) 25 12 37 48 33 57 86 92 (FLAG=1)
|
|
|
просмотр 4 (FLAG=0) 12 25 37 33 48 57 86 92 (FLAG=1)
просмотр 5 (FLAG=0) 12 25 33 37 48 57 86 92 (FLAG=1)
просмотр 6 (FLAG=0) 12 25 33 37 48 57 86 92 (FLAG=0).
Так как после 6-го просмотра признак обмена имеет значение 0, сортировка окончена.
1. 2. 1. 2. Просеивание (" челночная" сортировка)
Метод просеивания работает точно так же, как стандартный обмен до тех пор, пока не надо выполнять перестановку. Сравниваемая запись с меньшим ключом перемещается насколько это возможно к началу списка. Если ее ключ меньше, чем у предшественника, то выполняется обмен и начинается очередное сравнение.
Пример. Исходная последовательность
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)
25 57 48 37 12 92 86 33.
Первоначально, как и в методе " пузырька", сравниваются 1-й и 2-й элементы. Так как их порядок правильный, то они местами не меняются. Затем сравниваются 2-й и
3-й элементы. Так как 57 больше 48, то они меняются местами. При J=2 и I=2 последовательность будет иметь вид
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)
25 48 57 37 12 92 86 33.
Далее согласно алгоритму 2-й элемент сравнивается с 1-м. Порядок их правильный, и ничего не происходит.
Затем снова, как в методе " пузырька", сравниваются 3-й и 4-й
элементы. Они меняются местами. 3-й
элемент сравнивается со 2-м, и они также меняются. 2-й элемент сравнивается с 1-м, и так как порядок их правильный, они остаются на своих местах. После завершения этапа при J=3 последовательность будет иметь следующий вид:
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)
25 37 48 57 12 92 86 33.
После изменения значения переменной внешнего цикла J последовательность будет выглядеть следующим образом:
К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)
J=4 12 25 37 48 57 92 86 33
J=5 12 25 37 48 57 92 86 33
J=6 12 25 37 48 57 86 92 33
J=7 12 25 33 37 48 57 86 92.
Для ускорения работы алгоритма при каждом возврате регистрируется факт наличия или отсутствия обмена. Возврат, в результате которого не было произведено ни одного обмена, заканчивает просмотр. Структурограмма алгоритма сортировки методом просеивания представлена на рис. 2.
|
|
|
