ГРУППИРОВКА МАССИВА МЕТОДОМ ПРЯМОГО ОБМЕНА

Рассматриваемый метод группировки называют также методом "пузырька".

Запишем сверху вниз элементы :

Просмотр 1 Просмотр 2 Просмотр 3 . . . Просмотр n-1

…… …….. ……

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

Во втором просмотре анализируются пары элементов и , и , ... , и . Вследствие этого самый тяжелый из оставшихся элементов опустится на новое дно, т.е. займет место элемента .

В третьем просмотре анализируются пары элементов и , и , ... , и и т.д.

Работа алгоритма заканчивается, если при очередном просмотре будет определено, что ни разу не имело места нарушение упорядоченности элементов массива, т.е. ни разу не было выполнено условие .

Program Bubble;

Const Nmax = 500;

TypeAr = array[1..Nmax] of real;

Vari,n,m : word;

R : real;

Cond : boolean;

X : Ar;

Begin

Ввод и печать n,X

Cond:=true; m:=n;

While Cond do

Begin

Cond:=false;

Fori:=1 to m-1 do

Ifx[i]>x[i+1] then

Begin

R:=x[i]; x[i]:=x[i+1]; x[i+1]:=r;

Cond:=true;

End;

Dec(m);

End;

Печать Х

End.

Комментарии к программе.

1. Так как количество просмотров заранее неизвестно, то для их перебора используется цикл While, работающий под управлением булевской переменной Cond. После входа в цикл этой переменной присваивается значение false в предположении, что массив уже сгруппирован. После этого в цикле For проверяется справедливость этого предположения. Если обнаружено нарушение упорядоченности, то производится обмен смежных элементов, а переменной Cond присваивается значение true, что влечет за собой повторение работы цикла While, т.е. выполнение очередного просмотра.

2. Как было указано выше, после каждого просмотра уменьшается количество анализируемых элементов массива. Поскольку при этом нельзя изменять переменную n, определяющую количество элементов в исходном массиве, то для этой цели применяется буферная переменная m.

Сравним работу двух алгоритмов группировки.

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

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

Вывод. Метод "пузырька" следует применять в том случае, когда исходный массив частично упорядочен; в общем случае метод наименьшего элемента более эффективен.

Примечание. Кроме рассмотренных выше методов сортировки существуют также другие методы, работающие на порядок быстрее за счет определенного усложнения алгоритма. К таким методам относятся метод Шелла, метод быстрой сортировки и др.