Embedded Files
Пригадаємо!
Сортування елементів списку реалізується за допомогою методу sort(), який має таку загальну структуру: sort([key= None],[reverse = False]). Як бачимо, параметри є необов’язковими. За замовчуванням сортування виконується за зростанням значень елементів з урахуванням регістра.
Для сортування за зменшенням слід указати другий параметр таким: reverse=True. Зазначимо, що метод sort() перетворює старий список у новий.
Метод sorted(послідовність, [key=None],[reverse=False]) — призначений для сортування списку та збереження старого.
Для сортування з урахуванням регістру символів в методі sort() використовують в якості параметра функцію для зміни регістру символів у параметрі key.
Сортування - впорядковування набору однотипних даних по зростанню або спаданню. Мета сортування - полегшити подальший пошук елементів у такому відсортованому масиві.
Відмінною особливістю сортування є та обставина, що ефективність алгоритмів, що реалізують її, прямо пропорційна складності розуміння цього алгоритму. Іншими словами, чим легше для розуміння метод сортування масиву, тим нижче його ефективність.
Алгори́тм сортува́ння — в інформатиці — процес, що впорядковує множину однотипних елементів за певною ознакою (ключем сортування). Сортування є типовою проблемою обробки даних, що забезпечує розміщення елементів невпорядкованого набору значень в порядку монотонного зростання або спадання значення ключа.
Основні характеристики алгоритмів сорування:
час, необхідний на впорядкування множини з n елементів;
обсяг оперативної пам’яті для виконання сортування;
стабільність: чи змінює сортування взаємне розташування елементів із однаковими ключами.
Квадратичними називають алгоритми, у яких для повного сортування максимальна кількість операцій, які виконуються, дорівнює квадрату кількості його елементів. Тобто якщо масив містить n елементів, то для виконання алгоритму сортування потрібно виконати до n^2 операцій.
Класифікація квадратичних алгоритмів сортування:
• сортування підрахунком;
• сортування вставленням (включенням);
• сортування вибором;
• сортування обміном.
Сортування вибором — простий алгоритм сортування лінійного масиву. Для цього в масиві, розпочинаючи з першого, вибирається найбільший елемент і ставиться на перше місце, а перший – на місце найбільшого. Потім, розпочинаючи з другого, ця процедура повторюється.
Ідея:
•знайти мінімальний елемент і поставити на місце першого (поміняти місцями з A[1])
•із решти знайти мінімальний елемент і поставити на друге місце (поміняти місцями з A[2]), і т.д.
Нехай дано масив: mas[0], mas[1], ... , mas[n], який необхідно упорядкувати в порядку зростання значень його елементів. Розглянемо сутність алгоритму сортування вибором.
Процес упорядкування масиву чисел розглянемо на прикладі 1.
Програма реалізації алгоритму методом вибору зображено на рисунку:
У результаті виконання програми отримаємо: 3, 9, 17, 21, 33, 40.
Перевага описаного методу сортування полягає в його простоті. Проте він є найповільнішим (не враховується те, що в заданому масиві деякі елементи можуть бути впорядковані). Навіть якщо певний масив буде повністю впорядкованим, кількість операцій порівняння в алгоритмі не зменшиться.
Практичне завдання
Практичне завдання
Увага! Під час роботи з комп'ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.
Приклад 2. Задано масив А із 10 випадкових натуральних чисел. Впорядкуйте його за допомогою сортування вибором.
Результат виконання програми:
Page updated
Google Sites
Report abuse