Упорядкування та пошук даних в лінійний таблиці

Для повторення вивченого матеріалу виконати інтерактивну вправу

Переглянути відеопрезентацію

Опрацювати теоретичний матеріал

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

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

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

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

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

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

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

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

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

Як прискорити пошук елемента в лінійній таблиці?

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

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

Для ознайомлення із цим методом доцільно уточнити властивості еле­ментів таблиці — вони мають бути впорядковані за зростанням. Позна­чимо шуканий елемент масиву (списку) змінною х.

Можливі два випадки:

• якщо х менший від елемента, розташованого посередині масиву (списку), тоді завдяки впорядкованості таблиці можна не розглядати всі елементи, розташовані правіше від середнього, і застосувати цей метод до лівої половини таблиці;

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

Таким чином, на кожному кроці відсікається та частина таблиці, де не може бути знайдено заданий елемент х.

Розглянемо суть методу на прикладі. Наприклад, знайдемо, чи є серед елементів таблиці з іменем а з 10 цілих чисел, впорядкованих за зростанням, значення х = 6

         Знайдемо номер елемента, що міститься посередині таблиці: m = 5. Оскільки 6 < а[5], то далі розглядаються лише елементи, індекси яких менші ніж 5. Про інші елементи можна відразу сказати, що вони більші за х, оскільки таблиця впорядкована за зростанням, і тому правіше від а[5] шуканого елемента немає. Далі розглядатимемо тільки елементи та­блиці від а[1] до а[4], знаходимо індекс середнього елемента цієї частини: m = 2, і порівнюємо задане число 6 з елементом а[2].

         Виявляється, що 6 > а[2]. Це означає, що необхідно розглядати праву частину цієї половини таблиці від а[3] до а[4]. Знову знаходимо індекс се­реднього елемента m = 3 й порівнюємо його із шуканим: а[3] = 6. Елемент m знайдено — його номер 3.

Дайте відповідь на запитання онлайн вікторини