Алгоритм В

18 19 20 21 22 23 24

Пример программы с городами и файлами.

Алгоритм Б.

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

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

I=2; 1 2 3 4 5

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

1, 2, 3, 4, 5

Т.е. сократили число сравнений в каждом из просмотров.

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

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

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

Пример.

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. Очень медленный метод, т.к. сравнения и обмены

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

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

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

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

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

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

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

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