Методи сортування масивів

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

Клас List у Python має метод sort(), який упорядковує список за зростанням. Якщо потрібно упорядкувати елементи масиву за спаданням, після сортування застосовують метод reverse().

ПРИКЛАД 1. Упорядкувати елементи списку arr за незростанням.

# a = [81, 45, 23, 21, 12, 8, 7, 6, 4, 3]

Щоб зрозуміти сутність алгоритмів сортування, розглянемо два найпростіші методи сортування масиву. Нехай потрібно впорядкувати елементи списку arr із 10 елементів за неспаданням:

Сортування вибором максимального елемента

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

Алгоритм сортування (див. рисунок):

• Відшукати максимальний елемент у зрізі arr[0: 9].

• Максимальний елемент цього зрізу поміняти місцями з arr[9].

• Відшукати максимальний елемент у зрізі arr[0: 8].

• Максимальний елемент цього зрізу поміняти місцями з arr[8].

<...>

Максимальний елемент зрізу arr[0: 1]. Поміняти місцями з arr[1].

Реалізуємо алгоритм у вигляді функції. Список arr заповнимо 10 випадковими числами.

# При кожній ітерації циклу переглядається зріз [0: k]

# Знайшли максимальний елемент у зрізі arr[0: k]

# Визначили індекс максимального елемента

# Максимальний елемент поміняли місцями з останнім у зрізі

# Заповнення списку випадковими числами

# Виклик функції сортування

Сортування обміном (метод бульбашки)

Метод бульбашки — це метод упорядкування списку шляхом

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

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

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

Реалізуємо алгоритм у вигляді функції.

ПРИКЛАД 2. Проаналізуємо виконання алгоритму на прикладі списку arr = [5, 10, 1, 4, 6].

Уже на третій ітерації елементи виявились упорядкованими за зростанням, змінна prap = False, тому зовнішній цикл припиняє роботу. Для різних наборів значень списку може знадобитися різна кількість кроків сортування.

Питання для самоперевірки

1. У чому полягає сутність сортування методом вибору максимального елемента?

2. У чому полягає сутність сортування методом бульбашки?

3. Де може знаходитися найбільший елемент списку, якщо список не впорядковано?

4. Де може знаходитися найменший елемент списку, якщо список упорядковано за зростанням; за спаданням?

5.

Для кожної пари сусідніх елементів

списку а виконується операція

Початкове значення s дорівнює 0. Визначте, чому дорівнює кінцеве значення s, якщо список:

а) було впорядковано за зростанням;

б) було впорядковано за спаданням;

в) не було впорядковано.

6. Дано список результатів забігу на 100 м восьми спортсменів. Складіть програму для визначення трьох кращих результатів.

Вправа 32

Скласти програму для розв’язування задачі.

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

1) Створіть Python file із назвою Оцінки. Завантажте модуль random:

import random

2) Створіть порожній список grades.

3) Додайте до списку 9 випадкових чисел з інтервалу (4, 6). Щоб згенерувати випадкове дійсне число, викличте метод random.uniform(4, 6) і округліть згенероване число до 1 десяткового знаку:

Виведіть список на екран.

4) Упорядкуйте список. Виведіть упорядкований список на екран.

5) Знайдіть середнє арифметичне елементів, що утворюють зріз списку згідно з умовою задачі.

6) Виведіть результат з одним десятковим знаком.

Комп’ютерне тестування

Виконайте тестове завдання 32 з автоматичною перевіркою результату.

 

 

Це матеріал з підручника Інформатика 9 клас Бондаренко 2022