Сортировка обменом («пузырьковая сортировка»)

 

Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются. Далее берутся два следующих соседних элемента и так далее до конца массива. После одного такого прохода на последний 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 шаг:

 

Результат:

 

 

 

БЛОК – СХЕМА

	I = 2

 

 

Æ 1

 

 

K = M

 

 

Æ 1

 

I = I + 1

1 Æ

R = A(K-1) A(K-1)=A(K) A(K) = R

 

 

 

K = K-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, который содержал бы все элементы исходных массивов, упорядоченных по возрастанию.

Алгоритм решения этой задачи известен как «сортировка фон Неймана» или сортировка слиянием. Идея алгоритма состоит в следующем. Сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные.

 

 

Программа, реализующая метод Фон-Неймана, имеет следующий вид:

 

БЛОК – СХЕМА

 

 

	I = 1 J = 1 K = 1

Æ 1

1 Æ

 

1 Æ

1 Æ

 

[(K)=A(I)] I = I+1 K = K+1

[(K)=B(J)] J = J+1 K = K+1

K=N+M+1

[(K)=B(J)] J = J+1 K = K+1

[(K)=A(I)] I = I+1 K = K+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-

 

Двумерные массивы.