Примечание. Этот вид сортировки отличается от обменной тем, что за каждый проход большого цикла захватывается различное количество элементов массива, на каждом шаге более тяжелые опускаются на одну позицию вниз, а более легкие поднимаются на одну позицию вверх. Собственно тоже самое происходит и в обменной сортировке, но там на каждом шаге большого внешнего цикла обработке подвергается весь массив. Трудоемкость пузырьковой сортировки ограничена числом N*(N-1)/2. Пузырьковая сортировка обладает свойством устойчивости.
Program Z;
uses crt;
var a:array[1..100] of integer;
i,j,n,c:integer;
begin
clrscr;
write('количество элементов массива ');
read(n);
for i:=1 to n do read(a[i]);
for i:=n-1 downto 1 do
for j:=1 to i do if a[j]>a[j+1] then begin c:=a[j];
a[j]:=a[j+1];a[j+1]:=c;
end;
for i:=1 to n do write(a[i],' ');
end.
Пример. Сортировка обменом по возрастанию массива a из n целых чисел.
Рrogram Sort_Obmen;
var а:array[1..100] of integer;
n,i,k,x : integer;
begin write('количество элементов массива ');
read(n);
for i:=1 to n do read([i]);
for k:=n-1 downto 1 do {количество сравниваемых пар}
for i:=1 to k do if a[i]>a[i+1] then {меняем местами соседние элементы}
begin
x:=a[i];
a[i]:=a[i+1];
a[i+1]:=x;
end;
for i:=1 to n do write(a[i],' '); {упорядоченный массив}
end.
Наряду с сортировкой методом пузырька, существуют и некоторые другие, более эффективные методы сортировки: быстрая сортировка, метод Шелла, сортировка вставками... Однако рассмотренный алгоритм наиболее прост в реализации и логичен.
Приведем, тем не менее, процедуру "быстрой сортировки", которая шаг за шагом ищет максимальный, второй по величине и т.д. элементы и переносит: их в конец массива. Остановка цикла произойдет тогда, когда при очередном проходе не произойдет (т.е., элементы встали на свои места):
Procedure FastSort(Var aa:Massive);
Var ii,kk,nn:byte;
Begin
nn:=n;
Repeat
For ii:=1 to nn-1 Do Begin
kk:=0
If (aa[ii]>aa[ii+1]) Then Begin
Swap (aa[ii],a[ii+1]);
Inc(kk);
End;
End;
Dec(nn);
Until (kk=0);
End;
В то время, как при сортировке предыдущем методом для массива из 10 элементов понадобится 9 проходов, для данного алгоритма это число может уменьшиться. К примеру, массив из значений (1,-3,7,-10,11,4,-6,2,5,-4) будет отсортирован за 8 проходов, а массив (1,4,3,2,4,5,6,7,10,11) – всего за 1.
Следуя похожей, логике отсортируем массив по возрастанию: