Кафедра ЕОМ
Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування.
Провести дослідження побудованого методу за такою схемою: 1). Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний). 2). Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування. 3). Дослідити метод cортування на стійкість. 4). Дослідити метод cортування на економність використання пам’яті. 5). Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.). 6). Дослідити ефективність методу. Для цього визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому ( 7). Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості. Зробити висновки про ефективність методу. 4.2. Вибір варіанту індивідуального завдання
№ варіанта = [(місяць народження) + (ASCII–код другої літери прізвища – мала латинська літера)] % 30 + 1 4.3. Варіанти завдань 1. Сортування методом простого обміну (або методом бульбашки). 2. Сортування методом простого вибору. 3. Сортування методом простої вставки. 4. Сортування методом підрахунку порівнянь [1, 94-97 c.]. 5. Сортування методом підрахунку розпреділення [1, 97-98 c.]. 6. Сортування з обчисленням адреси [1, 118-121 c.], [2, 469-472 c.]. 7. Обмінне сортування зі злиттям [1, 131-133 c.]. 8. Обмінне порозрядне сортування [1, 144-150 c.]. 9. Сортування методом двохшляхового злиття [1, 181-182 c.]. 10. Сортування методом природного двохшляхового злиття [1, 183-185 c.]. 11. Сортування методом простого двохшляхового злиття [1, 186-187 c.]. 12. Сортування методом злиття списків [1, 187-189 c.]. 13. Порозрядне сортування списку [1, 195-200 с.] 14. Сортування за допомогою вставок і злиття [1, 208-210 c.]. 15. Сортування методом квадратичного вибору [3, 71-72 c.]. 16. Швидке сортування [3, 72-73 c.]. 17. Розподільне сортування [3, 73-75 c.]. 18. Бітове сортування [3, 75 c.]. 19. Бінарне сортування [3, 75-76 c.]. 20. Сортування злиттям списків [3, 76 c.]. 21. Сортування злиттям [3, 76-78 c.]. 22. Сортування вставками, що використовує бінарний пошук [2, 473 c., 495-497 с.]. 23. Сортування Шелла, що використовує кроки 7, 5, 3 і 1 [2, 466-469 c.]. 24. Сортування Шелла, що використовує кроки 13, 4 і 1 [2, 466-469 c.]. 25. Сортування двохшляховими вставками [2, 472-473 c.]. 26. Сортування злиттям вставок [2, 473 c.]. 27. Сортування простим злиттям [2, 474-477 c.]. 28. Порозрядне обмінне сортування [2, 477-478 c.]. 29. Порозрядне сортування [2, 478-481 c.]. 30. Сортування бінарним злиттям [2, 482 c.].
5. ЗМІСТ ЗВІТУ I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номеру варіанта. II. В звіті мають бути відображені наступні пункти: 1. Мета роботи. 2. Постановка задачі. 3. Опис алгоритму сортування. 4. Результати виконання програми. 5. Дослідження методу. Обґрунтування вибору структури даних. Схема алгоритму cортування. Дослідження на стійкість. Дослідження на економність використання пам’яті. Дослідження на специфіку вхідної послідовності. Дослідження ефективності методу. а) Кількість порівнянь в найкращому, в найгіршому та в середньому випадках. б) Кількість перестановок в найкращому, в найгіршому та в середньому випадках. в) Визначення класу (підкласу) до якого належить досліджуваний алгоритм. г) Обчислення функції трудомісткості. д) Висновок про ефективність методу Висновки. Додатки (тексти програм з коментарями). 6. КОНТРОЛЬНІ ПИТАННЯ 1. Що таке функція впорядкування? 2. Який алгоритм сортування називається сталим? 3. Які типи методів сортування існують у залежності від типу пам'яті, що використовується? 4. Що таке економне використання пам'яті? 5. Класифікуйте методи сортування масивів за принципом дії. 6. Назвіть показники ефективності алгоритму сортування. 7. Викладіть основну ідею методу простого включення. 8. Наведіть характеристики якості методу простого включення (кількість порівнянь та обмінів). 9. Як можна модифікувати метод простого включення? 10. У чому полягає основна ідея методу простого вибору? 11. У чому полягає основна ідея методу простого обміну? 12. Наведіть дані про кількість порівнянь та обмінів для методів простого вибору та простого обміну. 13. Що таке метод "бульбашки"? 14. Які існують модифікації методу простого обміну? 15. Викладіть основну ідею методу шейкер-сортування? 16. У яких випадках шейкер-метод має перевагу над методом "бульбашки"? 7. КОНТРОЛЬНІ ЗАВДАННЯ
СПИСОК ЛІТЕРАТУРИ 1. Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. – М.: Изд.дом ”Вильямс”, 2001. – 832 с. 2. Ленгсам Й., Огенстайн М., Тененбаум А. Структура данных для персональных ЭВМ. –М.:Мир, 1989 - 560 с. 3. Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі. –К:Либідь, 1993 - 224 с.
Кафедра ЕОМ
Дослідження ефективності методів сортування Методичні вказівки до лабораторної роботи № 4
з дисципліни " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
для студентів напряму 6.050102 “Комп’ютерна інженерія”
Львів – 2011 Методичні вказівки до комплексу лабораторних робіт з дисципліни "AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А.Матвейчук – Львів: Видавництво НУ “Львівська політехніка”, 2011 – 12 с.
Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ
Відповідальний за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
|
) і в найгіршому (
) випадках. Середні значення кількості порівнянь (
) і кількості перестановок (
) визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей.
