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