Метод бульбашки

Розглянемо способи сортування. Сама тема сортування є однією з найбільш типових задач.

Є три способи сортування масивів:

- сортування вибором;

- сортування обміном;

- сортування вставкою.

Для кожного способу є багато алгоритмів, що відрізняються часом сортування, який злежить від числа операцій порівняння і операцій обміну.

Традиційно розрізняють внутрішнє сортування, яке обробляє дані оперативної пам’яті, і зовнішнє сортування, яке оперує з даними розміщеними на дисках.

Розглянемо сортування числового одномірного масиву.

Відсортувати числовий масив: 7, 3, 8, 4,8, 5, 9, 1.

Звичайне сортування: 1, 3, 4, 5, 7, 8, 8, 9,.

Адресне сортування: 7, 3, 8, 4, 8, 5, 9, 1.

5, 2, 6, 3, 7, 4, 8, 1 (адреса).

Існує багато різних алгоритмів сортування (сортування бульбашкою, сортування за допомогою дерева, пірамідальне сортування, швидке сортування (половинного поділу).

Розглянемо деякі з них в дещо видозміненому вигляді.

Метод бульбашки:

Опис:

Найпростіший і найпопулярніший із них - це “сортування бульбашкою”.

Назва його походить від образної інтерпретації, при котрій у процесі виконання алгоритму більш “легкі” елементи мало-помалу випливають на “поверхню”.

Нехай а – числовий масив

а(1), а(2),...,а(n)

Говорять, що елементи а(і) і а(j) із а утворюють інверсію, якщо і<j

і а(і)<а(j).

Алгоритм “сортування бульбашкою” складається в послідовних проглядах знизу вверх (від початку до кінця) масиву s і обміну місцями сусідніх елементів.

З даної програми по введеному числу n створюється масив, заповненням його з клавіатури.

Цикл від 1 до до n здійснює перестановку місцями елементів масиву. Перестановка здійснюється, поки масив не стане відсортованим, за що відповідає змінна s.

Відсортований масив виводиться на екран. “Сортування бульбашкою” не потребує для реалізації додаткової пам’яті. Однак через погані характеристики він має лише історичну цінність і навряд чи може бути рекомендована для практичного використання.

{алгоритм бульбашки}

var і,n,c,s:іnteger;

a:array[1..1000] of іnteger;

begіn

{Заповнення масиву}

wrіte ('N=');readln(n);

for і:=1 to n do begіn

read(a[і]);

end;

s:=1;

whіle s=1 do begіn

s:=0;

for і:=1 to n-1 do

іf a[і]>a[і+1] then begіn c:=a[і];a[і]:=a[і+1];a[і+1]:=c;s:=1;end;

end;

{Виведення елементів масиву}

wrіteln;

wrіteln('Масив');

for і:=1 to n do wrіte(a[і],' ');

end.

11)Обробка прямокутної таблиці.

Знайти максимальний і мінімальний елементи таблиці розміром NхN і поміняти їх місцями (виконати для заштрихованої області).

var a:array[1..100,1..100] of integer;

n,i,j,max,maxi,maxj,min,mini,minj:integer;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do read(a[i,j]);

max:=a[1,1];maxi:=1; maxj:=1;

min:=a[1,1];mini:=1; minj:=1;

for i:=1 to (n+1) div 2 do

for j:=1 to i do begin

if a[i,j]>max then begin max:=a[i,j];maxi:=i;maxj:=j; end;

if a[i,j]<min then begin max:=a[i,j];mini:=1;minj:=j; end;

end;

for i:=n div 2 to n do

for j:=i downto 1 do begin

if a[i,j]>max then begin max:=a[i,j];maxi:=i;maxj:=j; end;

if a[i,j]<min then begin max:=a[i,j];mini:=1;minj:=j; end;

end;

writeln(maxi,maxj);

a[maxi,maxj]:=min;

a[mini,minj]:=max;

for i:=1 to n do begin

for j:=1 to n do write(a[i,j]:4);

writeln;

end;

end.

Домашнє завдання.

Запитання: