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

 

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

 

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

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться:

Популярное:

1. Обменом мы будем называть отчуждение и присвоение прав собственности на те или иные блага между двумя или большим числом агентов, обусловленное их осознанным взаимодействием.
2. Создание базы данных, поиск, сортировка и выборка информации в MS Access
3. Сортировка естественным слиянием.
4. Сортировка методом прямого включения
5. Сортировка методом прямого обмена
6. Сортировка многофазным слиянием.
7. Сортировка модели на топологическом ранге неопределенности
8. Сортировка сбалансированным слиянием