4. Завдання на лабораторну роботу
4.1. Вибір варіанта індивідуального завдання
Введемо позначення: DN – день народження
MN – місяць народження
А1 – ASCII-код першої літери прізвища – велика латинська літера
№ варіанта = ( DN + MN + А1 ) % 25+ 1
4.2. Варіанти завдань
Загальна частина:
Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування.
Провести дослідження побудованого методу за схемою:
1) Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний).
2) Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування.
3) Дослідити метод cортування на стійкість.
4) Дослідити метод cортування на економність використання пам’яті.
5) Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
6) Дослідити ефективність
методу. Для цього програмно визначити
значення кількості порівнянь (С) і
кількості перестановок (М) в найкращому
(
)
і в найгіршому (
)
випадках. Середні значення кількості
порівнянь (
)
і кількості перестановок (
)
визначити, як середнє арифметичне для
кожної величини від великої кількості
спроб сортування випадкових послідовностей.
Побудувати графіки залежностей
,
,
,
від кількості елементів n,
де n змінюється
від 1 до 100 000.
7) Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості.
Індивідуальні завдання:
Сортування методом простої вставки.
Сортування просіюванням з барьером.
Сортування бінарною вставкою.
Сортування методом простого вибору.
Сортування методом простого обміну.
Шейкер-сортування.
Сортування Шелла, що використовує кроки 9, 5, 3 і 1
Сортування Шелла, що обчислює послідовність приростів по першій формулі.
Сортування Шелла, що обчислює послідовність приростів по другій формулі.
Пірамідальне сортування.
Швидке сортування.
Сортування злиттям.
Порозрядне сортування.
Бітове сортування.
Сортування методом підрахунку порівнянь [1, 94-97 c.].
Сортування методом підрахунку розпреділення [1, 97-98 c.].
Сортування з обчисленням адреси [1, 118-121 c.], [2, 469-472 c.].
Обмінне сортування зі злиттям [1, 131-133 c.].
Обмінне порозрядне сортування [1, 144-150 c.].
Сортування методом двохшляхового злиття [1, 181-182 c.].
Сортування методом природного двохшляхового злиття [1, 183-185 c.].
Сортування методом простого двохшляхового злиття [1, 186-187 c.].
Сортування методом злиття списків [1, 187-189 c.].
Порозрядне сортування списку [1, 195-200 с.]
Сортування за допомогою вставок і злиття [1, 208-210 c.].