Особенность шейкер-сортировки заключается в том, что в отличие
от стандартного обмена запоминается не только факт обмена, но и теку-
щая позиция обмена, а просмотры чередуются попеременно в противо-
положных направлениях в некотором интервале. монеты
На 1-м просмотре производится сравнение ключей соседних запи-
сей, например слева направо, начиная с первой позиции, и фикси-
руется позиция L последнего обмена. На 2-м просмотре сравниваются
ключи соседних записей справа налево, начиная с L-го элемента, и
фиксируется позиция R последнего обмена. В результате 2-х просмотров
запись с наибольшим ключом займет N-ю позицию, а запись с наименьшим ключом - 1-ю. Затем снова слева направо сравниваются ключи соседних записей, начиная с R-й позиции и кончая L-й и т.д. Сортировка заканчивается, если в результате очередного просмотра не производился обмен.
Структурограмма алгоритма шейкер-сортировки приведена на рис. 3.
При программировании: одна процедура - просто шаг разный.
Пример.
5, 4, 1, 2, 3
R=1, L=5, FLAG=0;
I=1; 4 5 1 2 3
I=2; 4 1 5 2 3
I=3; 4 1 2 5 3
I=4; 4 1 2 3 5;
M=4, FLAG=1;
L=4, FLAG=0;
I=4; 4 1 2 3 5
I=3; 4 1 2 3 5
I=2; 1 4 2 3 5;
M=2, FLAG=1;
R=2, FLAG=0;
I=2; 1 2 4 3 5
I=3; 1 2 3 4 5
M=3, FLAG=1;
L=3, FLAG=0;
I=3; 1 2 3 4 5;
R=3.
Найти характеристики.
Все по обменным сортировкам.
