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

За новою програмою

Урок 31

9

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

Розділ 6 § 18

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

Зростанням

Неспаданням

Спаданням

Зростанням

якщо значення елементів не повторюються

якщо значення елементів можуть повторюватись

9

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

Розділ 6 § 18

Правило (ознака), за яким виконують впорядкування елементів, називають ключем впорядкування. У словниках ключами є самі слова, впорядковані в лексикографічному порядку (тобто у відповідності до порядку літер в алфавіті).

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

Дати, як правило, впорядковуються за ключем «рррр.мм.дд»,

де рррр — рік, мм — місяць, дд — день.

9

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

Розділ 6 § 18

Основним при організації впорядкування є визначення відношення порядку на множині елементів,

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

9

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

Розділ 6 § 18

Існує багато різних методів впорядкування, які відрізняються один від одного ступенем ефективності.

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

9

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

Розділ 6 § 18

Розглянемо один з методів впорядкування лінійної таблиці — метод вибору.

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

9

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

Розділ 6 § 18

Далі знаходять елемент із найменшим значенням з решти

n - 1 елементів

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

9

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

Розділ 6 § 18

Таким чином, для прикладу таблиці з 5 елементів, яка містить значення довжини п'яти олівців, послідовно розглядають чотири різні набори олівців (чотири таблиці, що мають різну довжину):

9

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

Розділ 6 § 18

З кожним набором елементів виконуються однакові дії:

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

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

9

Розділ 6 § 18

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

9

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

Розділ 6 § 18

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

9

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

Розділ 6 § 18

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

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

9

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

Розділ 6 § 18

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

9

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

Розділ 6 § 18

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

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

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

9

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

Розділ 6 § 18

(Продовження…) Можливі два випадки:

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

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

9

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

Розділ 6 § 18

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

X=6

9

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

Розділ 6 § 18

Знайдемо номер елемента, що міститься посередині таблиці:

Оскільки 6<а[5], то далі розглядаються лише елементи, індекси яких менші ніж 5. Про інші елементи можна відразу сказати, що вони більші за х оскільки таблиця впорядкована за зростанням, і тому правіше від а[5] шуканого елемента немає.

m=5

Далі розглядатимемо тільки елементи таблиці від а[1] до а[4], знаходимо індекс середнього елемента цієї частини:

m=2

і порівнюємо задане число 6 з елементом а[2].

9

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

Розділ 6 § 18

Виявляється, що 6>а[2]. Це означає, що необхідно розглядати праву частину цієї половини таблиці від а[3] до а[4].

Знову знаходимо індекс середнього елемента

m=3

І порівнюємо його з шуканим: а[3]=6. Елемент m знайдено — його номер 3.

9

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

Розділ 6 § 18

У програмах мовою програмування Python для прискорення пошуку можна використати вбудовані засоби мови, зокрема ідеологію побудови циклу for, у якому замість індексів елементів можна переглядати самі елементи, наприклад, у команді циклу

For elem in a:

Змінна elem «пробігатиме» всі елементи списку а.

9

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

Розділ 6 § 18

Можна не переглядати елементи списку, а просто перевірити входження елемента elem у список а за допомогою фрагмента програми:

If elem in a:

print (‘Елемент належить списку' ).

9

Розгадайте ребус

навпіл

Розділ 6 § 18

Ділення

9

Домашнє завдання

Проаналізувати

§ 18, ст. 142-148

Розділ 6 § 18

9

Працюємо за комп’ютером

Розділ 6 § 18

Сторінка

143-146

9

Дякую за увагу!

За новою програмою

Урок 31

9