- •Лабораторна робота №1 «Cтрокові змінні в середовищі програмування Delphi»
- •3 Теоретичний матеріал
- •4 Варіанти завдань для виконання
- •Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №2 «Робота з чергою та стеком»
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №3 «Розробка програми створення зв'язаного списку»
- •3 Теоретичний матеріал
- •4 Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №4
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №5 «Побудова рекурсивних функцій»
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •5 Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №6 «Бінарне дерево пошуку»
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •5 Хід виконання практичної роботи
- •Питання до захисту :
- •Лабораторна робота №7 «Реалізація алгоритмів обмінних сортувань»
- •3 Теоретичний матеріал
- •4 Вихідні дані роботи
- •5 Хід виконання практичної роботи
- •Питання до захисту :
Питання до захисту :
Перерахуйте подібності та відмінності динамічних структур типу «лінійний список», «стек», «дерево».
Відповідь:____________________________________________________
_____________________________________________________________
Написати процедуру, яка визначає глибину дерева.
Відповідь:____________________________________________________
_____________________________________________________________
Який тип інформації зручно представляти за допомогою бінарних дерев?
Відповідь:____________________________________________________
_____________________________________________________________
Чому пошук на бінарних деревах не дає виграшу по складності в порівнянні з лінійними структурами?
Відповідь:____________________________________________________
_____________________________________________________________
Роботу виконав Роботу перевірив
Лабораторна робота №7 «Реалізація алгоритмів обмінних сортувань»
1 Тема роботи: Реалізація алгоритмів обмінних сортувань при написанні програм в середовищі Delphi.
2 Мета роботи: Формування знань і умінь по вивченню методів внутрішніх сортувань. Придбання навичок реалізації алгоритмів сортування.
3 Теоретичний матеріал
Алгоритм сортування - це алгоритм для впорядкування елементів у списку. У випадку, коли елемент списку має кілька полів, поле, що служить критерієм порядку, називається ключем сортування. На практиці в якості ключа часто виступає число, а в решті полях зберігаються які-небудь дані, ніяк не впливають на роботу алгоритму.
Класифікація алгоритмів сортування
Стійкість (stability) - стійка сортування не змінює взаємного розташування рівних елементів.
Природність поведінки - ефективність методу при обробці вже впорядкованих або частково впорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.
Використання операції порівняння. Алгоритми, що використовують для сортування порівняння елементів між собою, називаються заснованими на порівняннях. Мінімальна трудомісткість гіршого випадку для цих алгоритмів становить O (n logn), але вони відрізняються гнучкістю застосування. Для спеціальних випадків (типів даних) існують більш ефективні алгоритми.
Ще однією важливою властивістю алгоритму є його сфера застосування. Тут основних типів упорядкування два:
Внутрішня сортування оперує масивами, цілком поміщається в оперативній пам'яті з довільним доступом до будь комірці. Дані зазвичай упорядковуються на тому ж місці без додаткових витрат.
Існує три групи методів внутрішнього сортування (сортування включенням, сортування вибором, обмінна сортування).
У сучасних архітектурах персональних комп'ютерів широко застосовується підкачка і кешування пам'яті. Алгоритм сортування повинен добре поєднуватися з застосовуваними алгоритмами кешування і підкачки.
Зовнішня сортування оперує запам'ятовуючими пристроями великого об'єму, але з доступом не довільним, а послідовним (впорядкування файлів), тобто в даний момент ми 'бачимо' тільки один елемент, а витрати на перемотування в порівнянні з пам'яттю невиправдано великі. Це накладає деякі додаткові обмеження на алгоритм і призводить до спеціальних методів впорядкування, зазвичай використовують додатковий дисковий простір. Крім того, доступ до даних на носії виробляється набагато повільніше, ніж операції з оперативною пам'яттю.
Доступ до носія здійснюється послідовним чином: в кожний момент часу можна вважати або записати тільки елемент, наступний за поточним.
Обсяг даних не дозволяє їм розміститися в ОЗУ.
Також алгоритми класифікуються за:
потребою в додатковій пам'яті або її відсутності
потребою в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності такої
