Лабораторна робота № 11 (13)

Тема: Створення та реалізація програм опрацювання табличних величин. Сортування таблиць методом прямого вибору.

Мета: Уміти створювати та реалізовувати програми опрацювання табличних величин, опрацьовувати масиви за умовою.

Теоретичні відомості

Розглянемо npocтi алгоритми упорядкування (сортування) одновимірних таблиць. Мета сортування - полегшити наступний пошук елементів. Bи6ip алгоритму сортування залежить від структури оброблюваного списку. Критеріями ефективності сортування є швидкодія й економія пам'яті, що може бути важливим у разі великих списків.

Метод прямого вибору. Скажімо, вам потрібно з вихідної послідовності А [i], що складається з N елементів, утворити спадну послідовність (точніше, послідовність з незростаючих елементів). Зафіксуємо перший елемент i переглянемо інший масив (N-і) елементів, відшукавши в ньому найбільший. Якщо цей елемент виявиться більшим від першого, поміняємо його місцями з першим елементом. Потім зафіксуємо елемент 2 i переглянемо (N-2) елементи, що залишились. Знайшовши найбільший елемент, поміняемо його з елементом 2. Подібну процедуру продовжуватимемо, поки не залишиться один, найбільший, елемент.

Наведемо програму мовою Pascal, що здійснює сортування масиву з 5 еле-ментів (рядків) методом прямого вибору:

Program SortSelect;

const Num=5;

A: array[l..Num] of string=('ca', 'aa', 'd^і, 'a', 'ab^і);

Var Temp: string; I, J, L: integer;

begin

Writeln ('Начальный массив');

for I: =l to Num do

Write (' ', A[I]);

Writeln; Writeln;

for I: =l to Num-і do

for J: =I+і to Num do

begin

if A[I]< A[J] then

begin

Temp: =A[I]; A[I]: =A[J]; A[J]: =Temp;

end;

for L: =l to Num do Write(' ', A[L]); Writeln;
end; end.

Процес сортування в цьому прикладі проілюструємо виведенням одержуваної послідовності елементів після кожної операції порівняння.

Неважко підрахувати, що кількість операцій порівняння в методі прямого вибору дорівнюватиме числу комбінацій з Nmах по 2, тобто Nmax! / (2! (Nmax- 2)!), де Nmax - розмір початкового масиву.

Хід роботи

1. Запишіть програму формування одновимірного масиву з рядунатуральних чисел.

2. Застосуйте програму сортування для упорядкування одновимірного масиву, що містить натуральні числа.

3. Застосуйте програму сортування для упорядкування двовимірного масиву, що містить символи латинського алфавіту.

4. Застосуйте програму сортування для упорядкування одновимірного масиву, що містить слова.

Контрольні запитання

1. Як увести значення елементів масиву за допомогою оператора for?

2. Як виконується пошук елементів у масиві?

3. Які методи сортування масивів вам відомі?

4. У чому полягає метод прямого вибору?

5. В чому полягає різниця в описанні програми сортування між спаданням і зростанням елементів?

6. Як ви розумієте поняття спадання і зростання для символьних типів величин?