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

https://inf9-m.blogspot.com/2017/11/blog-post_26.html 

Як упорядковувати дані в деякому наборі?

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

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

Правило (ознака), за яким виконують впорядкування елементів, називають ключем впорядкування. 

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

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

Методів впорядкування списку — метод вибору.

Уявімо, що дані містяться в таблиці. 

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 елементів, послідовно розглядають чотири різні набори даних (внутрішній цикл)(чотири таблиці, що мають різну довжину): 

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

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

ПЕРШИЙ СПОСІБ

Для впорядкування набору даних від найменшого до найбільшого можна скористатись ідеєю створення нового списку, у який по черзі буде з вихідного списку вилучатись найменше та додаватись до нового. Розглянемо алгоритм на прикладі, де а — вихідний список, а b — новий, упорядкований:

У результаті виконання відповідної програми (мал.14.2) отримуємо результат:

a = []

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

Читати підручник