Інформатика

Прочитайте!

Виконайте вправу 1

Виконайте вправу 2

Одновимірний масив вважається впорядкованим, якщо серед значень його елементів встановлено певний порядок. Наведемо кілька прикладів впорядкованих одновимірних масивів:

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

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

Розрізняють 4 види впорядкованості одновимірного масиву за значеннями його елементів: за зростанням, за спаданням, за неспаданням, за незростанням.

Одновимірний масив a називається впорядкованим за зростанням (зростаючим), якщо значення кожного його наступного елемента більше значення попереднього, тобто для всіх і виконується нерівність a[i+1] > a[i]. Наприклад, впорядкованим
за зростанням (зростаючим) є масив: 5; 12; 32; 44,5; 88; 101.
Одновимірний масив a називається впорядкованим за спаданням (спадним), якщо значення кожного його наступного елемента менше значення попереднього, тобто для всіх і виконується нерівність a[i+1] < a[i]. Наприклад, впорядкованим за спаданням (спадним) є масив: 45; 32; 22; 4,5; 0; –7. Одновимірний масив a називається впорядкованим за неспаданням (не спадним), якщо значення кожного його наступного елемента не менше (більше або дорівнює) значення попереднього, тобто для всіх і виконується нерівність a[i+1] ≥ a[i]. Наприклад, впорядкованим за неспаданням (неспадним) є масив: 15; 22; 22; 34; 40; 40.

Одновимірний масив a називається впорядкованим за незростанням (незростаючим), якщо значення кожного його наступного елемента не більше (менше або дорівнює) значення попереднього, тобто для всіх і виконується нерівність a[i+1] ≤ a[i]. Наприклад, впорядкованим за незростанням (незростаючим) є масив: 35; 12; 12; 7; 7; 1.

Алгоритми впорядкування одновимірних масивів

Алгоритми перетворення невпорядкованих одновимірних масивів у впорядковані називаються алгоритмами впорядкування (сортування) одновимірних масивів. Таких алгоритмів існує досить багато. Ми розглянемо два з них: впорядкування методом вибору і впорядкування методом обміну.

Впорядкування одновимірного масиву методом вибору

Розглянемо алгоритм впорядкування одновимірного масиву методом вибору. Будемо впорядковувати масив за зростанням.

Пояснимо ідею цього алгоритму на прикладі. Використовуючи цей алгоритм впорядкуємо масив з 6 чисел: 23; 7; 4;  16;  -2;  10.

Звертаємо вашу увагу, що на останньому кроці виконання алгоритму свої місця зайняли одразу два елементи масиву.
Отже, ми мали одновимірний масив з 6 чисел. І ми 5 разів виконували такі дії:

1. Вибирали найменший елемент серед елементів поки що невпорядкованої частини масиву.
2. Обмінювали цей вибраний елемент з першим елементом поки що невпорядкованої частини масиву.

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

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

Звертаємо вашу увагу:
Щоб впорядкувати одновимірний масив за спаданням, потрібно на кожному кроці у невпорядкованій поки що частині масиву вибирати не найменший елемент, а найбільший.
Якщо в одновимірному масиві є рівні між собою елементи, то наведений алгоритм впорядкує його за неспаданням. Переконайтеся в цьому разом з однокласником/однокласницею на прикладі масиву: 12; 4; 6; 2; 6; 4.

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

Завдання 3. Використовуючи метод вибору відсортуйте масив за спаданням: -4; 7; -9; 0; 5; 19; 3; -8.