Алгоритм А

Метод стандартного обмена

Этот метод основан на попарном сравнении ключей соседних

записей. Если порядок следования записей в очередной паре неправилен, то эти элементы обмениваются местами. Монеты

При 1-м просмотре ключ 1-й записи сравнивается с ключом 2-й записи, и, если 2-й меньше, они меняются местами. Затем ключ, расположенный во 2-й позиции, сравнивается с ключом из 3-й позиции. Обмен происходит, если меньший из них находится в 3-й позиции. После этого позиция 3 сравнивается с позицией 4, позиция 4 с позицией 5 и т.д. Когда позиция N-1 сравнивается с позицией N, просмотр заканчивается.

Важная особенность. После первого просмотра запись с наибольшим ключом займет N-ю позицию, а минимальный элемент переместится на одну позицию к началу последовательности.

Второй и последующие просмотры идентичны.

Так как на каждом из просмотров очередные наибольшие элементы

занимают, соответственно, позиции N, N-1, N-2 и т.д., то не более

как за N-1 просмотр исходная последовательность будет упорядочена.

5, 4, 1, 2, 3

J=1, 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

J=2, I=1; 1 4 2 3 5

I=2; 1 2 4 3 5

I=3; 1 2 3 4 5

I=4; 1 2 3 4 5

J=3, I=1; 1 2 3 4 5

I=2; 1 2 3 4 5

I=3; 1 2 3 4 5

I=4; 1 2 3 4 5

J=4, I=1; 1 2 3 4 5

I=2; 1 2 3 4 5

I=3; 1 2 3 4 5

I=4; 1 2 3 4 5

1, 2, 3, 4, 5

Второй просмотр идентичен первому лишь с той разницей, что он

заканчивается после сравнения ключей (N-2)-й и (N-1)-й записей.

Поэтому можно сократить число сравнений в просмотрах