Алгоритми впорядкування масиву

 Як упорядковувати дані в лінійній таблиці?

Для розв’язування багатьох задач зручно спочатку впорядкувати дані за певною ознакою. Наприклад, пошук елемента в масиві чи списку можна значно прискорити, якщо відповідні дані впорядковані. При цьому ознакою такого впорядкування може бути за зростанням (якщо значення елементів не повторюються), за неспаданням (якщо значення елементів можуть повторюватись), за спаданням, за незростанням.

Правило (ознака), за яким виконують впорядкування елементів, називають ключем впорядкування. У словниках ключами є слова, впорядковані в лексикографічному порядку (тобто відповідно до порядку літер в алфавіті). Список учнів впорядковано за ключем, що відповідає їх номеру в алфавітній книзі школярів. Дати переважно впорядковуються за ключем «рррр.мм.дд», де рррр — рік, мм — місяць, дд — день. Основним при організації впорядкування є визначення відношення порядку на множині елементів, яка впорядковується, тобто для будь-яких двох елементів цієї множини важливо визначити, який з них слідує за іншим, передує іншому або що вони збігаються.

Є багато різних методів впорядкування, які відрізняються один від одного ступенем ефективності. Ступінь ефективності враховує кількість порівнянь та кількість обмінів, які виконано під час впорядкування: що меншою є така кількість, то ефективнішим є метод впрорядкування.

Розглянемо один з методів впорядкування лінійної таблиці — метод вибору. За таким методом спочатку з набору з довільним розташуванням елементів вибирають елемент із найменшим значенням i виконують його взаємозаміну зі значенням у першій клітинці таблицi, — таким чином у першій клітинці таблиці розташовується найменше значення вмісту клітинок таблиці. Далі знаходять елемент із найменшим значенням з решти n – 1 елементiв i виконують його взаємозаміну з вмістом клітинки з номером два i т. д. Потім розглядаються елементи, що лишилися, серед яких знову знаходять найменший, який потім міняють місцями з вмістом третьої клітинки. Таким чином, для прикладу таблиці з 5 елементів, яка містить значення довжини п’яти олівців, послідовно розглядають чотири різні набори олівців (чотири таблиці, що мають різну довжину): у першому наборі було п’ять елементів, у другому — чотири, у третьому — три, у четвертому — два. З кожним набором елементів виконують однакові дії:

·         у наборі вибирають найменший елемент, запам’ятовують його номер у такому наборі (таблиці);

·         знайдений найменший елемент міняють місцями з першим елементом набору, що розглядається.

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

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

 

Вправа 1. Упорядкування масиву.

Завдання. Створіть проект Упорядкування, у якому елементи лінійної таблиці з 10 цілих чисел впорядковуються за зростанням.

Розробка проекту в середовищі програмування Lazarus

1. У папці Навчальні проекти своєї структури папок створіть папку Упорядкування.

2. Відкрийте середовище Lazarus і створіть новий проект. Розмістіть на екранній формі  об’єкти, самостійно надайте значення їхнім властивостям.

3. Створіть процедуру опрацювання події Упорядкувати. У вікні редактора коду опишіть змінні, які будуть використовуватись у проекті: а — масив цілих чисел; i — номер ітерації пошуку мінімального елемента масиву;  j — номер елемента масиву; min — найменше значення елемента; nmin — номер найменшого елемента.

var    i, j, min, nmin : integer;

а : array [1..10] of integer;

4. У вікні редактора коду запишіть команди введення елементів масиву в багаторядкове текстове поле, впорядкування елементів та їх виведення в багаторядкове текстове поле

5. Запустіть проект на виконання. Перевірте, чи відповідають умові завдання дії, пов’язані з об’єктами управління екранної форми. Якщо є помилки, виправте їх. Завершіть роботу з проектом і середовищем програмування, зберігши всі зміни.