Алгоритмізація процесу сортування

 

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

Із сортуванням пов’язано багато фундаментальних прийомів побудови алгоритмів. Розглянемо сортування масивів[4,5].

Маємо елементи:

.

Процес сортування означає здійснення перестановки даних елементів у наступному порядку:

,

тобто за заданої функції впорядкування f справедливим є відношення

 

.

 

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

Основною вимогою до методів сортування масивів є економне використання пам'яті, а отже, під час обрання методу сортування слід керуватися критерієм економії пам’яті. У зв’язку з цим класифікацію алгоритмів будемо проводити відповідно до їх ефективності, тобто економії часу або швидкодії.

Зручну міру ефективності отримуємо за допомогою підрахунку чисел С (кількості необхідних порівнянь) та М (кількості пересилань елементів). Ці числа визначаються деякими функціями від числа n (кількості елементів), що сортуються. Більш ефективні алгоритми сортування потребують порядку n∙log n порівнянь, але спочатку розглянемо кілька нескладних та очевидних способів сортування, які мають назву простих методів і потребують порядку n² -порівнянь.

Методи для сортування елементів in situ можна розбити на три основних класи залежно від прийому, закладеного в основу методу:

1) сортування методом включень;

2) сортування методом обрання;

3) сортування методом обміну [2-4].

 

 

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

 

1 Описати етапи розв’язання задач за допомогою ЕОМ.

2 Охарактеризувати властивості алгоритмів.

3 Навести способи опису алгоритмів.

4 Для чого призначені блоки структурного опису алгоритмів?

5 Охарактеризувати лінійний обчислювальний процес.

6 Перелічити складові елементи арифметичного виразу.

7 Дати визначення понять «константа» та «змінна».

8 Охарактеризувати розгалужений обчислювальний процес.

9 Охарактеризувати циклічний обчислювальний процес.

10 Сформулювати мету сортування.

11 Перелічити методи сортування.

Лабораторна робота 1

ПОБУДОВА ЛІНІЙНИХ АЛГОРИТМІВ

 

Мета – ознайомитись з прийомами алгоритмізації лінійних обчислюваних процесів, навчитись будувати лінійні алгоритми розв’язання математичних задач.

 

Завдання для підготовки до виконання лабораторної роботи

Формалізувати обчислювальний процес розв’язання математичної задачі за індивідуальним варіантом та побудувати блок-схему лінійного обчислювального процесу.

Під час виконання лабораторної роботи студент повинен знати мету виконання лабораторної роботи, порядок її виконання та загальні теоретичні положення; вміти будувати блок-схеми лінійних обчислювальних процесів.

 

ЗАГАЛЬНІ положення

 

Лінійним прийнято називати обчислювальний процес, операції якого виконуються послідовно, в порядку їх запису. Кожна операція є самостійною та не залежить від будь-якої вимоги. Блоки, що відображають такі операції, на схемі розташовуються в лінійній послідовності.

Лінійні обчислювальні процеси застосовуються під час обчислення арифметичних виразів.

 

Приклад розв’язання здачі. Скласти схему алгоритму

Вивести на друк M, a.

Розв’язання. Умови задачі не передбачають перевірки будь-яких умов або повторення виконання операцій розрахунків, тому обчислюваний процес для розв’язання задачі є лінійним.

Перш ніж будувати блок-схему необхідно дати відповіді на наступні питання наведені далі.

1 Значення яких параметрів надані (тобто є константами в даній задачі)?

2 Значення яких змінних повинен внести користувач?

3 Значення яких змінних розраховуються та в якому порядку?

4 Значення яких змінних слід вивести на екран?

Задача, що розв’язується, має такі відповіді:

1 b =21.4;

2 F, K, q;

3 a, c, M;

4 a, M.

Блок-схему алгоритму лінійного обчислюваного процесу, побудовану за вказаними принципами зображено на рисунку 1.

 

 

Рисунок 1 – Алгоритм лінійного обчислюваного процесу

Блок 1 та 8 зображеної блок-схеми – це блоки початку та кінця алгоритму, 2 та 7 – блоки вводу/виводу даних, 3 – блок присвоєння, 4-6 – блоки розрахунків.