Пример программы с городами и файлами.
Алгоритм Б.
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. Число обменов (перестановок) зависит от степени упорядоченности исходного набора данных:
минимальное - 0;
максимальное - N*(N-1)/2.
3. Дополнительный объем памяти требуется для переменной FLAG
и для запоминания одной записи при реализации операции обмена.