Embedded Files
Посилання на завантаження файлу інсталяції середовища прорамування для мови Python: https://www.python.org/downloads/windows/
Посилання на завантаження файлу інсталяції середовища прорамування для мови Python: https://www.python.org/downloads/windows/
Одновимірний масив вважається впорядкованим, якщо серед значень його елементів встановлено певний порядок. Наведемо кілька прикладів впорядкованих одновимірних масивів:
• список учнів вашого класу на кожній сторінці класного журналу впорядкований в алфавітному порядку;
• список слів в орфографічному або тлумачному словнику також впорядковані в алфавітному порядку.
Одновимірні масиви впорядковують перш за все для того, щоб пошук необхідних даних у них відбувався значно швидше, ніж у впорядкованих.
Розрізняють 4 види впорядкованості одновимірного масиву за значеннями: за зростанням, за спаданням, за неспаданням, за незростанням.
Одновимірний масив а називається впорядкованим за зростанням, якщо значення кожного його наступного елемента більше значення попереднього, тобто для всіх і виконується нерівність a[i+1]>a[i]. Наприклад, впорядкованим за зростанням (зростаючим) є масив: 5;12; 32; 44,5; 88; 101.
Одновимірний масив а називається впорядкованим за спаданням, якщо значення кожного його наступного елемента менше значення попереднього, тобто для всіх і виконується нерівність a[i+1]<a[i]. Наприклад, впорядкованим за спаданням (спадним) є масив: 45; 32; 22; 4,5; 0; –7.
Одновимірний масив а називається впорядкованим за неспаданням, якщо значення кожного його наступного елемента не менше (більше або дорівнює) значення попереднього, тобто для всіх і виконується нерівність a[i+1]>=a[i]. Наприклад, впорядкованим за неспаданням (неспадним) є масив: 15; 22; 22; 34; 40; 40.
Одновимірний масив а називається впорядкованим за незростанням, якщо значення кожного наступного елемента не менше (більше або дорівнює) значення попереднього, тобто для всіх і виконується нерівність a[i+1]<=a[i]. Наприклад, впорядкованим за незростанням (незростаючим) є масив: 35; 12; 12; 7; 7; 1.
Алгоритми перетворення невпорядкованих одновимірних масивів у впорядкований називаються алгоритмами впорядкування (сортування) одновимірних масивів. Таких алгоритмів існує досить багато.
Впорядкування одновимірного масиву методом вибору
Розглянемо алгоритм впорядкування одновимірного масиву методом вибору. Будемо впорядковувати масив за зростанням.
Ідея:
•знайти мінімальний елемент і поставити на місце першого (поміняти місцями з A[1]).
•із решти елементів масиву знову знайти мінімальний елемент і поставити на друге місце (поміняти місцями з A[2]), і т.д.
Отже, ми мали одновимірний масив з 6 чисел: 23, 7, 4, 16, -2, 10. І ми 5 разів виконували такі дії:
1. Вибирали найменший елемент серед елементів поки що невпорядкованої частини масиву.
2. Обмінювали цей вибраний елемент з першим елементом поки що невпорядкованої частини масиву.
Звертаємо вашу увагу, що на останньому кроці виконання алгоритму свої місця зайняли одразу два елементи масиву.
Розглянемо фрагмент проєкту для впорядкування за зростанням списку з 6 дійсних чисел, що вводяться з клавіатури, методом вибору:
Практичне завдання
Увага! Під час роботи з комп'ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.
Задача 1. Складемо проєкт для впорядкування за зростанням списку з n дійсних чисел, що вводяться з клавіатури, методом вибору:
Звертаємо вашу увагу:
1. Щоб впорядкувати одновимірний масив за спаданням, потрібно на кожному кроці у невпорядкованій поки що частині масиву вибирати не найменший елемент, а найбільший. Для цього необхідно внести певні зміни у фрагмент проєкту.
2. Якщо в одновимірному масиві є рівні між собою елементи, то наведений алгоритм впорядкує його за неспаданням.
Задача 2. Скласти проєкт для сортування методом вибору за спаданням елементів одновимірного масиву з 10 цілих чисел.
Задача 3. В одновимірному масиві зберігаються оцінки учнів групи з інформатики. Впорядкуйте цей масив і визначить, скільки учнів має найнижчу в цій групі оцінку.
Задача 4. Скласти проєкт для сортування методом вибору за неспаданням/незростанням елементів одновимірного масиву з 10 дійсних чисел.
Page updated
Google Sites
Report abuse