ДМ Лабораторна робота 1. Методи сортування елементів множини
 Скачать 273.63 Kb.
|
|
Лабораторна робота 1 Тема: методи сортування елементів множини. Мета: ознайомитися з методами сортування елементів множини. Теоретичні відомості 1. Бульбашковий метод 1.1. Приклад реалізації крок за кроком Візьмемо масив чисел «5 1 4 2 8», і за допомогою даного алгоритму, відсортуємо його від найменшого до найбільшого елементу. На кожному кроці, елементи, виділені жирним шрифтом будуть порівнюватись. Перший прохід: (5 1 4 2 8) → (1 5 4 2 8) Тут, алгоритм порівнює перші два елементи, і міняє їх місцями. (1 5 4 2 8) → (1 4 5 2 8) (1 4 5 2 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 4 2 5 8) Тут порівнювані елементи знаходяться на своїх місцях, тож алгоритм не міняє їх місцями. Другий прохід: (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8) Тепер наш масив повністю відсортований, однак, алгоритм цього ще не знає. Йому потрібен ще один «пустий» прохід, під час якого він не поміняє місцями жодного елементу. Третій прохід: (1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8) Нарешті, масив відсортовано, і алгоритм може припинити свою роботу. 1.2. Опис алгоритму 1) Прохід по неупорядкованій множині (наприклад, списку). При цьому, якщо наступний елемент менше попереднього, то вони міняються місцями. В результаті найбільший елемент опиниться в кінці множини. 2) Прохід по множині, за виключенням останнього елементу, оскільки він вже відсортований. Під час проходу виконуємо обмін меншего наступного на більший попередній. 3) Кількість проходів по множині дорівнює кількості елементів мінус 1. Останній прохід не потрібний, оскільки залишається один елемент, і його значення менше за всі інші. Він «піднявся» за рахунок попередніх проходів. 2. Сортування вибором 2.1. Алгоритм працює таким чином: 1. Знаходить у списку найменше значення. 2. Міняє його місцями із першим значеннями у списку. 3. Повторює два попередніх кроки, доки список не завершиться (починаючи з наступної позиції). Фактично, таким чином ми поділили список на дві частини: перша (ліва) — повністю відсортована, а друга (права) — ні. 2.2. Ось приклад сортування масиву з п'яти елементів за даним алгоритмом: 64 25 12 22 11 11 25 12 22 64 11 12 25 22 64 11 12 22 25 64 Порядок виконання роботи Скласти комп’ютерні програми реалізації методів сортування (бульбашковий метод, сортування вибором) для масивів розмірності n (n=10,100,…,100000). Побудувати графік часу виконання сортування в залежності від кількості елементів множини для кожного методу. Зауваження. Визначення часу виконання програми: from time import time %%time |