• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

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

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

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

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

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

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

Відсортувати числовий масив: 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.

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

Запитання:

1. Опис таблиці.
2. Робота з таблицею (введення, виведення).
3. Алгоритм пошуку максимального (мінімально) елементів.
4. Алгоритм сортування в порядку зростання (спадання).
5. Двомірний масив та його опрацювання.

Читайте також:

1. D) методу мозкового штурму.
2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
3. I Метод Шеннона-Фано
4. I. Метод рiвних вiдрiзкiв.
5. VII. Нахождение общего решения методом характеристик
6. А. науковий факт, b. гіпотеза, с. метод
7. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
8. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
9. АгротехнІЧНИЙ метод
10. Адаптовані й специфічні методи дослідження у журналістикознавстві
11. Адміністративні (прямі) методи регулювання.
12. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.

Переглядів: 2573