Учебно-методическое пособие. Алматы, 2017 ббк

3.1.2. Сортировка обменом.

Следующий метод сортировки основан на сравнении двух элементов:

1. Сравниваем первые два элемента. Если первый элемент меньше второго, то меняем их местами.

2. Сравниваем второй и третий, третий и четвертый, ..., предпоследний и последний, при необходимости меняя их местами. Самый маленький окажется на последнем месте.

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

procedure Bubble(var item: DataArray; count:integer);

var

i,j: integer;

begin

begin

if item[j-1]>item[j] then

begin

x := item[j-1];

item[j] := x;

end;

end;

Можно несколько улучшить этот алгоритм. Можно заметить, что для ряда случаев, когда массив уже отсортирован, программа делает дополнительные просмотры. Что бы избежать этого, мы можем запоминать, были или не были перестановки в процессе некоторого прохода. Если в последнем проходе перестановок не было, то работу можно закончить.

Можно сделать еще одно улучшение, если запоминать не только сам факт, что обмен имел место, но и положение (индекс) последнего обмена. Все пары соседних элементов дальше этого индекса К и уже находятся в требуемом порядке. Поэтому следующий просмотр можно заканчивать на этом индексе, а не идти до заранее определенного индекса N-i.

Будем использовать переменную Р (логического типа) для определения, были перестановки или нет, а переменную К - для хранения индекса последнего обмена. Переменная R является границей, на которой заканчивается просмотр.

var

x: DataItem;

s: Boolean;

begin

s:=true;

if item[i]< item [i+1] then

begin

s:=false;

item[i]:= item[i+1];

item[i+1]:=x;

end;

end;