Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются. Далее берутся два следующих соседних элемента и так далее до конца массива. После одного такого прохода на последний n-ой позиции массива будет стоять максимальный элемент («всплыл первый пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1 элемента. И так далее. Всего требуется n-1 проход.
1 шаг:
3 11
7 11 2 11 9 11
2 шаг: 1 11 4 11
  5
|
3 5 1 7
4 7
3 шаг: 2 7
1 5
4 5
4 шаг: 2 5
1 3 2 4
5 шаг:
 1
|
2 3
6 шаг:
7 шаг:
Результат:
БЛОК – СХЕМА
|
 |
Æ 1
|
Æ 1
|
1 Æ
|
|
 | |||
 |
Программа реализирующая метод обмена («пузырька»), будет иметь следующий вид:
Program Duddle Sort;
Uses Crt;
Const
N = 20; { длина массива}
Type
TVector = array [1…n] of Real;
Var
Vector : Tvector;
B : Real;
i, K : Integer;
begin
ClrScr;
Writeln (‘введите элементы массива:’);
for i: = 1 to n do Read (Vector [i]); Readln;
{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }
for K: = n downto 2 do
{“всплывание” очередного максимального элемента}
{на К-ю позицию}
for i: = 1 to K-1 do
if Vector [i] > Vector [i+1] then
begin
B: = Vector [i];
Vector [i]: = Vector [i+1];
Vector [i+1]: = B;
End;
{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }
Writeln (‘отсортированный массив:’);
For i: = 1 to n do Write (‘Vector [i]: 8 : 2’);
Writeln;
End.
Результат работы:
| Bведите элементы массива: Отсортированный массив: |
Сортировка фон Неймана (слиянием)
Заданы два упорядоченных по возрастанию элементов одномерных массива: а размерности n и b размерности m. Требуется получить третий массив с размерности n+m, который содержал бы все элементы исходных массивов, упорядоченных по возрастанию.
Алгоритм решения этой задачи известен как «сортировка фон Неймана» или сортировка слиянием. Идея алгоритма состоит в следующем. Сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные.
Программа, реализующая метод Фон-Неймана, имеет следующий вид:
БЛОК – СХЕМА
|
Æ 1
1 Æ
 |  | ||
1 Æ
1 Æ
| |  | ||||
 | |||||
|
|
|
 |  |
|
|
program confluence;
const n = 10;
m = 20;
l = n + m;
var x: array [1..n] of integer;
y: array [1..m] of integer;
z: array [1..l] of integer;
k, i, j: integer;
begin
for i: = 1 to n do
read (x[i]); {формирование первого упорядоченного массива}
for i: = 1 to m do
read (y[i]); {формирование второго упорядоченного массива}
I:= 1; j:=1; l:=1 {i-индекс первого массива, j-индекс второго
массива, l-индекс результирующего массива}
while (i<=n) and (j<=m) do {пока не закончились элементы в одном из массивов}
if x[i] < y[i] then {переписываем элементы из первого массива}
begin
z[k]: = x[i];
i: = i + 1; k: = k + 1;
end
else {переписываем элемент из второго массива}
begin
z[k]: = y[j];
j: = j + 1; k: = k + 1;
end;
while i < = n do {если не закончились элементы в первом массиве,}
begin {переписываем их в результирующий массив}
z[k]: = x[i]; i: = i + 1; k: = k+1;
end;
while j < = m do {если не закончились элементы во втором массиве}
begin {переписываем их в результирующий массив}
z[k]: = y[j]; j: = j + 1; k: = k+ 1;
end;
for i: = 1 to l do {вывод на экран упорядоченного массива,}
writeln (z[i]); {полученного слиянием}
End.
Результаты работы:
Шейкер-сортировка
Шейкер — сортировка является модификацией сортировки методом пузырька. Здесь, как и в методе пузырька проводят попарное сравнение элементов и обменов в паре. Если имеется необходимость, но первый проход осуществляют снизу вверх, второй – сверху вниз и т.д. Иными словами меняется направление прохода.
program sheyker;
uses crt;
const n=30;
var a:array[1..n]of integer;
x,j,i,u:integer;
h:boolean;
begin
clrscr;
writeln('Массив до сортировки:');
for i:=1 to n do
begin
a[i]:=round(random*999);
write(a[i],'-');
end;
writeln;
writeln('Массив после сортировки:');
h:=true;u:=n;i:=2;
repeat
if h then begin
for j:=u downto i do
if a[j-1]>a[j] then begin
x:=a[j-1];
a[j-1]:=a[j];
a[j]:=x;
h:=false;
end;
u:=u-1;
end
else begin
for j:=i to u do
if a[j+1]<a[j] then begin
x:=a[j+1];
a[j+1]:=a[j];
a[j]:=x;
h:=true;
end;
i:=i+1;
end;
until u=i;
for i:=1 to n do
write(a[i],'-');
readln;
end.
Результаты выполнения программы:
| Массив до сортировки: 0-31-860-202-273-671-318-162-372-425-82-474-70-840-60-293-916-368-774-328-697-84 3-717-306-162-329-466-246-825-279- Массив после сортировки: 0-31-60-70-82-162-162-202-246-273-279-293-306-318-328-329-368-372-425-466-474-67 1-697-717-774-825-840-843-860-916- |
Двумерные массивы.