Інформатика – Поглиблений рівень

Пригадаємо!

Завдання 1. Складіть програму, яка переводить число з двійкової системи числення в десяткову. Перевірте виконання програми на таких числах: 10(2), 100000(32), 1100110011(819), 111111(63), 111000111(455).

Сортування списку
Відсортувати список дозволяє метод sort(). Метод має такий вигляд: sort([key = None] [, reverse = False])
Всі параметри є необов’язковими. Метод змінює поточний список і нічого не повертає. Відсортуємо список по зростанню з параметрами за замовчуванням:\

Щоб відсортувати список за спаданням, слід в параметрі reverse вказати значення True:

При сортуванні фактично порівнюються два об’єкти, і який з них “менше”, ставиться перед тим, який “більше”. Поняття “більше” і “менше” досить умовні. І якщо для чисел все просто – числа розставляються в порядку зростання, то для рядків і інших об’єктів ситуація складніша. Зокрема, рядки оцінюються по перших символах. Якщо перші символи рівні, оцінюються другі символи і так далі. При чому цифровий символ вважається “менше”, ніж алфавітний заглавний символ, а заглавний символ вважається меншим, ніж рядковий. Детальніше ми це розглянемо при вивченні рядків.
Таким чином, якщо в списку поєднуються рядки з верхнім та нижнім регістром, то ми можемо отримати не зовсім коректні результати, так як для нас рядок “bob” повинен стояти до рядка “Tom”. І щоб змінити стандартну поведінку сортування, ми можемо передати в метод sort() в якості параметра функцію для зміни регістру символів у параметрі key:

Прочитайте!

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

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

Нині є десятки різних методів сортування, які відрізняються кількісними характеристиками показників. Для того щоб обґрунтовано зробити свій вибір, існують параметри, за якими проводиться оцінка алгоритмів. Квадратичними називають алгоритми, у яких для повного сортування максимальна кількість операцій, які виконуються, дорівнює квадрату кількості його елементів. Тобто якщо масив містить n елементів, то для виконання алгоритму сортування потрібно виконати до n2 операцій. Розглянемо алгоритми сортування масиву вибором та обміном.

Класифікація квадратичних алгоритмів сортування:

•  сортування підрахунком;
•  сортування вставленням (включенням);
• сортування вибором;
•  сортування обміном.

Алгоритм сортування вибором

Нехай дано масив: mas[0], mas[1], … , mas[n], який необхідно упорядкувати в порядку зростання значень його елементів. Розглянемо сутність алгоритму сортування вибором.

Процес упорядкування масиву чисел розглянемо на прикладі 1.

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

Програму реалізації алгоритму зображено на рисунку.

У результаті виконання програми отримаємо: 3, 9, 17, 21, 33, 40

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

Самостійне виконання вправ

Завдання 1. Проаналізуйте порядок виконання алгоритму сортування вибором на прикладі масиву 31, 20, 30, 35.

Завдання 2. Дано масив: ‘процесор’, ‘команда’, ‘флешка’, ‘брелок’, ‘клавіатура’. Виконайте сортування його елементів в алфавітному порядку за допомогою методу вибору.