Алгоритм В.

Для ускорения работы алгоритма в процессе сортировки при каждом просмотре регистрируется факт наличия или отсутствия обмена. Просмотр, в результате которого не было произведено ни одного обмена, заканчивает сортировку.

Структурограмма алгоритма сортировки методом стандартного

обмена приведена на рис.

Пример.

5, 4, 1, 2, 3

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

FLAG=1

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

I=2; 1 2 4 3 5

I=3; 1 2 3 4 5

FLAG=1

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

I=2; 1 2 3 4 5

FLAG=0

1, 2, 3, 4, 5

Т.е. сократили число просмотров.

Процедура реализации

procedure SortPuz (var K : array of Integer; N : Integer);var I,J,Temp : Integer; Flag : Boolean; Begin J:=1; repeat Flag := False; for I := 0 to N – J -1 do if K [I] > K [I + 1] then begin Temp := K [I]; K [I] := K [I + 1]; K [I + 1] := Temp; Flag := True; end; Inc(J); until Flag = False; end;

Метод "пузырька" характеризуется следующими параметрами.

Качественные:

1. Простот для понимания и легкий для программирования.

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

производятся только между соседними элементами.

1. Требуется наличие всех записей до начала сортировки.

2. Время на сортировку зависит от степени упорядоченности исходного набора данных

Количественные:

1. Число сравнений зависит от числа просмотров:

минимальное - (N-1);

максимальное - N*(N-1)/2.

2. Число обменов (перестановок) зависит от степени упорядоченности исходного набора данных:

минимальное - 0;

максимальное - N*(N-1)/2.

3. Дополнительный объем памяти требуется для переменной FLAG

и для запоминания одной записи при реализации операции обмена.

Вернуться в оглавление