Шейкер-сортировка

 

Особенность шейкер-сортировки заключается в том, что в отличие

от стандартного обмена запоминается не только факт обмена, но и теку-

щая позиция обмена, а просмотры чередуются попеременно в противо-

положных направлениях в некотором интервале. монеты

На 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.

 

Найти характеристики.

Все по обменным сортировкам.