Упорядкування та пошук даних в лінійній таблиці
Упорядкування та пошук даних в лінійній таблиці
Embedded Files
Як упорядковувати дані в деякому наборі?
Для розв’язування багатьох задач зручно спочатку впорядкувати дані за певною ознакою. Наприклад, пошук елемента в списку можна значно прискорити, якщо відповідні дані впорядковано.
При цьому ознакою такого впорядкування може бути за зростанням (якщо значення елементів не повторюються), за неспаданням (якщо значення елементів можуть повторюватись), за спаданням, за незростанням.
Правило (ознака), за яким виконують впорядкування елементів, називають ключем впорядкування.
У словниках ключами є самі слова, впорядковані в лексикографічному порядку (тобто у відповідності до порядку літер в алфавіті).
Список учнів за ключем, що відповідає їх номеру в алфавітній книзі школярів.
Дати, як правило, впорядковуються за ключем «рррр.мм.дд», де рррр — рік, мм — місяць, дд — день.
Основним під час організації впорядкування є визначення відношення порядку на множині елементів, яка впорядковується, тобто для будь яких двох елементів цієї множини важливо визначити, який з них слідує за іншим, передує іншому або що вони співпадають.
Існує багато різних методів впорядкування, які відрізняються один від одного ступенем ефективності. Ступінь ефективності враховує кільість порівнянь та кількість обмінів, які виконано під час впорядкування: що меншою є така кількість, то ефективнішим є метод впорядкування.
Методів впорядкування списку — метод вибору.
Уявімо, що дані містяться в таблиці.
За таким методом спочатку з набору з довільним розташуванням елементів вибирають елемент із найменшим значенням i виконують його взаємозаміну із значенням в першій клітинці таблицi — таким чином у першій клітинці таблиці розташовується найменше значення вмістів клітинок таблиці.
Далі знаходять елемент із найменшим значенням з решти n-1 елементiв i виконують його взаємозаміну з вмістом клітинки з номером 2, i т. д.
Потім розглядаються елементи, що лишилися, серед яких знову знаходять найменший, який потім міняють місцями з вмістом третьої клітинки.
import random
spysok =[]
for i in range (9):
spysok.append (random.randint(-10,10))
print (spysok)
for n in range(9):
m=spysok[n]
for nomer in range(n,9):
if m>=spysok[nomer ]:
m=spysok[nomer ]
a=nomer
k=spysok[n]
spysok[n]=spysok[a]
spysok[a]=k
print(spysok)
Таким чином,
для прикладу таблиці з 5 елементів, послідовно розглядають чотири різні набори даних (внутрішній цикл)(чотири таблиці, що мають різну довжину):
у першому наборі було п’ять елементів, у другому — чотири, у третьому — три, у четвертому — два. З кожним набором елементів виконуються однакові дії:
y в наборі вибирається найменший елемент, запам’ятовується його номер у такому наборі (таблиці);
y знайдений найменший елемент міняють місцями з першим елементом набору, що розглядається.
Наприклад, упорядкування даних у таблиці з п’яти цілих чисел продемонстровано на малюнку 14.1, де жовтим кольором виділено найменший елемент серед елементів, що залишаються для перегляду на кожному кроці, стрілками — порядок обміну елементами.
Зверніть увагу, що хоча таблиця має 5 елементів, достатньо 4 рази знайти найменше значення елементів з іще не впорядкованої частини лінійної таблиці та обміняти його місцями зі значенням першого зі ще не впорядкованої частини масиву елементів.
ПЕРШИЙ СПОСІБ
Для впорядкування набору даних від найменшого до найбільшого можна скористатись ідеєю створення нового списку, у який по черзі буде з вихідного списку вилучатись найменше та додаватись до нового. Розглянемо алгоритм на прикладі, де а — вихідний список, а b — новий, упорядкований:
У результаті виконання відповідної програми (мал.14.2) отримуємо результат:
У результаті виконання відповідної програми (мал.14.2) отримуємо результат:
a = []
a = []
b = [1, 2, 2, 4, 5]
b = [1, 2, 2, 4, 5]
#Задамо список
a =[5,2,1,4,2]
#Утворюємо порожній список
b=[]
#Опрацьовуємо список
for n in range(len(a)):
b=b+[min(a)]#У список в додали найменший елемент списку а
a.remove(min(a))# Із списку а видалили найменший елемент
#Виводимо результат
print('a=', a)
print('b=', b)
Вправа 1. Упорядкування списку.
Завдання. Створіть проєкт Упорядкування, у якому елементи списку з 10 цілих чисел впорядковуються за зростанням
3. У вікні редактора коду https://replit.com/ запишіть команди введення значень елементів списку, його упорядкування та виведення списку у вікні виконання програми. Використайте у проєкті змінні: spysok — список цілих чисел, nomer — номер ітерації пошуку мінімального елемента списку, n — номер
елемента списку
import random
spysok =[]
for i in range (9):
spysok.append (random.randint(-10,10))
print (spysok)
for n in range(9):
m=spysok[n]
for nomer in range(n,9):
if m>=spysok[nomer ]:
m=spysok[nomer ]
a=nomer
k=spysok[n]
spysok[n]=spysok[a]
spysok[a]=k
print('Результат впорядкування масиву')
print(spysok)
Один з результатів (кожного разу різний)
[5, -9, 8, 5, 10, 5, -4, -4, -2]
Результат впорядкування масиву
[-9, -4, -4, -2, 5, 5, 5, 8, 10]
>>>
Практичні завдання
Практичні завдання
Практичне завдання до уроку №42-3.pdfЧитати підручник
Читати підручник
Розділ 3; §14 стор.156-159 Інформатика. Підручник для 9 кл. / Н. В. Морзе, О. В. Барна.
Page updated
Google Sites
Report abuse