Лабораторна робота 8_Pascal

Лабораторна робота 8.

ПОШУК НАЙБІЛЬШОГО ТА НАЙМЕНШОГО ЕЛЕМЕНТІВ МАСИВУ. СОРТУВАННЯ МАСИВІВ.

Т е о р е т и ч н и й м а т е р і а л

Пошук найбільшого та найменшого елементів масиву.

Для цілого класу задач обробки масивів необхідно знати найбільший або найменший елемент масиву.

Завдання 1

Програма пошуку цих величин подана нижче: program max_min;

uses crt;

var n,i: integer; A: array [1..255] of real; max, min: real;

begin

clrscr;

write (‘ Введіть кількість елементів масиву: ‘); readln (n); for i:=1 to n do

begin

write (‘ Введіть a[‘, i, ‘] елемент масиву: ‘); readln (a[i]);

end;

clrscr;

writeln (‘ Програма пошуку найбільшого та найменшого елементів масиву ‘); writeln (‘ Заданий масив:’);

for i:=1 to n do write (a[i]:3:3, ‘ ‘); max:=a[1]; min:= a[1];

for i:=2 to n do begin

if a[i]<min then min:=a[i]; if a[i]>max then max:=a[i];

end; writeln; writeln;

writeln (‘ Мінімальний елемент масиву: ‘, min:3:3); writeln (‘ Максимальний елемент масиву: ‘, max:3:3); readln

Т е о р е т и ч н и й м а т е р і а л

Сортування масивів.

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

Для оцінки швидкодії алгоритмів різних методів сортування, як правило, використовують два показники:

кількість присвоювань;

кількість порівнянь.

Всі методи сортування можна розділити на дві великі групи:

прямі методи сортування;

поліпшені методи сортування.

Прямі методи сортування за принципом, що лежить в основі методу, у свою чергу розділяються на чотири групи:

Сортування обміном (метод «бульбашки»).

Сортування вибором (виділенням).

Сортування вставкою (включенням).

Сортування підрахунком.

Сортування обміном (метод «бульбашки»).

Принцип методу: Перегляд масиву здійснюється від кінця до початку. Якщо два сусідніх елемента не розташовані у порядку зростання, то вони міняються місцями. За один перегляд спливає одна «бульбашка». Необхідно виконати n-1 перегляд таблиці.

Завдання 2

Програма сортування масиву методом «бульбашки». program bulbashka;

uses crt;

var n,i,j: integer; A: array [1..255] of real; x: real;

begin

clrscr;

write (‘ Введіть кількість елементів масиву: ‘); readln (n); for i:=1 to n do

begin

write (‘ Введіть a[‘, i, ‘] елемент масиву: ‘); readln (a[i]);

end;

clrscr;

writeln (‘ Програма сортування масиву методом «бульбашки» ‘); writeln (‘ Заданий масив: ‘);

for i:=1 to n do write (a[i]:3:2, ‘ ‘); for i:=1 to n-1 do

for j:=n downto i+1 do if a[j]<a[j-1]

then begin

x:=a[j]; a[j]:=a[j-1]; a[j-1]:=x

end;

writeln; writeln;

writeln (‘ Відсортований масив: ‘); for i:=1 to n do write (a[i]:3:2, ‘ ‘); readln

end.

Т е о р е т и ч н и й м а т е р і а л

Сортування вибором (виділенням).

Принцип методу: Перший елемент порівнюється зі всіма іншими, які розташовані праворуч від нього. Якщо якійсь елемент по значенню менш, ніж перший, то вони міняються місцями. Після першого проходу масиву, виконують другий, починаючи перегляд з другого елементу та повторюючи попередні дії. Необхідно виконати n-1 перегляд таблиці.

Завдання 3

Програма сортування масиву методом вибору. program vybir;

uses crt;

var n,i,j: integer; A: array [1..255] of real; x: real;

begin

clrscr;

write (‘ Введіть кількість елементів масиву: ‘); readln (n); for i:=1 to n do

begin

write (‘ Введіть a[‘, i, ‘] елемент масиву: ‘); readln (a[i]);

end;

clrscr;

writeln (‘ Програма сортування масиву методом вибору ‘); writeln (‘ Заданий масив: ‘);

for i:=1 to n do write (a[i]:3:3, ‘ ‘); for i:=1 to n-1 do

for j:=i+1 to n do if a[j]<a[i]

then begin

x:=a[i];

a[i]:=a[j];

a[j]:=x

end;

writeln; writeln;

writeln (‘ Відсортований масив: ‘); for i:=1 to n do write (a[i]:3:3, ‘ ‘); readln

end.

Т е о р е т и ч н и й м а т е р і а л

Сортування вставкою (включенням).

Принцип методу: Масив розділяється на дві частини: відсортовану і невідсортовану. Елементи з невідсортованої частини по черзі вибираються і вставляються у відсортовану частину так, щоб не порушити в ній упорядкованість елементів. На початку роботи алгоритму в якості відсортованої частини масиву приймають тільки один перший елемент, а в якості невідсортованої – всі інші елементи. Таким чином, необхідно виконати n-1 перегляд таблиці, кожній з яких буде включати чотири дії:

узяття чергового невідсортованого елемента і збереження його в додатковій змінній;

пошук позиції у відсортованій частині масиву, у якій присутність узятого елемента не порушить упорядкованості елементів;

зсув елементів масиву вправо, щоб звільнити знайдену позицію вставки;

вставка взятого елемента в знайдену позицію.

Завдання 4

Програма сортування масиву методом вставки.

program vstavka; uses crt;

var n,i,j,k,p: integer; A: array [1..255] of real; x: real; w: boolean;

begin

clrscr;

write (‘ Введіть кількість елементів масиву: ‘); readln (n); for i:=1 to n do

Т е о р е т и ч н и й м а т е р і а л

Сортування підрахунком.

Принцип методу: У процесі виконання зберігається початковий масив та утворюється новий масив, який є упорядкованою копією першого. Перший елемент порівнюється зі всіма іншими, які розташовані ліворуч та праворуч від нього. Підраховується кількість елементів, які по значенню менш, ніж перший. Таким чином визначається місце цього елемента в новому масиві. Після першого проходу масиву, виконують другий, починаючи перегляд з другого елементу та повторюючи попередні дії. Необхідно виконати n переглядів таблиці.

Завдання 5

Програма сортування масиву методом підрахунку. program podschet;

uses crt;

var n,i,j,k: integer; A: array [1..255] of real; B: array [1..255] of real;

begin

clrscr;

write (‘ Введіть кількість елементів масиву: ‘); readln (n); for i:=1 to n do

begin

write (‘ Введіть a[‘, i, ‘] елемент масиву: ‘); readln (a[i]);

end;

clrscr;

writeln (‘ Програма сортування масиву методом підрахунку ‘); writeln (‘ Заданий масив: ‘);

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

begin

k:=0;

for j:=1 to n do if a[j]<a[i]

then k:=k+1;