Автор очень ответственно и профессионально подходит к выполнению заказов. Большое спасибо!
Информация о работе
Подробнее о работе
Лабораторна робота №3 з курсу "Теорія алгоритмів" Спеціальність: Інформаційні управляючі системи та технології
- 1 страниц
- 2017 год
- 106 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
-
-
КПИ (Киевский политехнический институт).
-
# -*- coding: utf-8 -*-
"""
Лабораторна робота №3 з курсу "Теорія алгоритмів"
Спеціальність: Інформаційні управляючі системи та технології
МЕТА:
Дослідити метод швидкого сортування.
ОПИС РОБОТИ:
В даній роботі досліджується алгоритм сортування методом швидкого
сортування (quick sort). Відомо, що в найгіршому випадку цей алгоритм
має асимптотичну складність O(n^2), проте математичне сподівання часу
роботи алгоритму (тобто, в середньому) становить O(n*lg(n)).
Втім у даного методу існує один недолік. Він полягає в тому, що метод
швидкого сортування критично залежить від опорного елементу в процедурі
розбиття (partition). Щоб обійти цю залежність пропонується опорний
елемент обирати випадково, таким чином отримуючи рандомізований
(впадковий) алгоритм швидкого сортування (randomized quick search).
В роботі пропонується визначити як впливає введення рандомізації на
швидкість алгоритму.
ЗАВДАННЯ:
1) Реалізований алгоритм сортування методом швидкого сортування. Для цього
написати функції quick_sort та partition на основі наведеного псевдокоду
(див. коментарії до функцій).
2) Реалізуваний рандомізована версія алгоритму у вигляді функцій
randomized_quicksort та randomized_partition (див. коментарі до функцій).
3) Порівняти роботи алгоритмів швидкого сортування та рандомізованого
швидкого сортування один з одним, а також із алгоритмом сортування методом
злиття та гібридного алгоритму, заснованого на сортуванні злиттям та
включенням (див. лабораторну роботу №2 та функцію
compare_merge_hybrid_quick). Рекомендовані параметри проведення експериментів:
- найбільший розмір вхідного масиву n: 5000-10000
- крок n для різних експериментів: 100-200
- кількість повторних викликів для фіксованого n: 50-100
На основі отриманих результатів зробити висновки щодо найкрашого алгоритму
сортування.
4) За допомогою методу швидкого сортування
розв'зати наступну задачу.
Гайки та болти. Неорганізований тесляр має змішаний набір N гайок та N болтів.
Ціль полягає в тому, щоб знайти відповідні пари гайок та болтів. Кожна
гайка відповідає точно одному болту і кожний болт відповідає точно одній
гайці. З'єднуючи гайку та болт між собою, тесляр може дізнатись хто з них
більший (проте він не може порівнювати безпосередньо дві гайки чи два болти).
Розробіть алгоритм для цієї задачі, який використовує в середньому NlogN
порівнянь.
Підказка: цю задачу можна звести до наступної. Є два масиви A та B, які
містять однакову кількість елементів N. Причому відомо, що елементи в
масивах однакові, проте знаходяться у довільному порядку. Необхідно
відсортувати обидва масиви, але при сортуванні можна порівнювати тільки
такі елементи, що один з них належить масиву A, а інший - масиву B.
Для рішення цієї задачі наповніть функції double_quick_sort та
double_partition
-
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
