|
|
Інститут прикладного системного аналізуСтр 1 из 3Следующая ⇒ Кафедра Системного проектування
Розрахунково-графічна робота з предмету: «Побудова та аналіз алгоритмів» на тему: «Порівняння алгоритмів сортування»
Виконав: студент групи ДА-12 ННК «ІПСА» Яременко Вадим Сергійович
Київ – 2012 Зміст
1.Вступ ………………………………………………………………………………………………………………………………3 2.Короткі теоретичні відомості ………………………………………………………………………………………..3 2.1 Алгоритм швидкого сортування ……………………………………………………………………...3 2.2 Алгоритм «бульбашкового» сортування …………………………………………………………3 3.Практична частина………………………………………………………………………………………………………...6 3.1 Програма реалізації алгоритму швидкого сортування …………………………………..6 3.2 Програма реалізації алгоритму «бульбашкового» сортування ………………………7 3.3 Дослідження швидкості сортування масиву (табличний варіант) ………………...8 3.4 Дослідження швидкості сортування масиву (графічний варіант)……………….. 10 4.Висновок ……………………………………………………………………………………………………………………….14 5.Список використаної літератури ………………………………………………………………………………….15
Вступ
Що таке алгоритм сортування? Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів. На сьогоднішній день проблема прискорення роботи алгоритмів є дуже важливою. Тому що розмір об’єму даних зростає з кожним днем, і тому часто трапляється так, що дуже швидкі алгоритми у свій час стають повільними. Вони виконують операції не хвилину-дві, а години, дні, місяці. Отже, у своїй роботі я буду досліджувати та аналізувати роботу двох алгоритмів сортування, а саме: алгоритму швидкого сортування та класичний алгоритм «бульбашкового» сортування. А саме, їх швидкодію, найкращі та найгірші випадки у їх роботі. Короткі теоретичні відомості Алгоритм швидкого сортування
Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам'яті і виконує у середньому Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв’язному списку. Аналіз алгоритму Час роботи алгоритму сортування залежить від збалансованості, що характеризує розбиття. Збалансованість, у свою чергу залежить від того, який елемент обрано як опорний (відносно якого елемента виконується розбиття). Якщо розбиття збалансоване, то асимптотично алгоритм працює так само швидко як і алгоритм сортування злиттям. У найгіршому випадку, асимптотична поведінка алгоритму настільки ж погана, як і в алгоритму сортування включенням. Найгірша поведінка має місце у тому випадку, коли процедура, що виконує розбиття, породжує одну підзадачу з n-1 елементом, а другу — з 0 елементами. Нехай таке незбалансоване розбиття виникає при кожному рекурсивному виклику. Для самого розбиття потрібен час
Розв'язком такого співвідношення є
Найгірше розбиття Найгірша поведінка має місце у тому випадку, коли процедура, що виконує розбиття, породжує одну підзадачу з n-1 елементом, а другу — з 0 елементами. Нехай таке незбалансоване розбиття виникає при кожному рекурсивному виклику. Для самого розбиття потрібен час
Розв'язком такого співвідношення є Найкраще розбиття В найкращому випадку процедура розділенення масиву ділить задачу на дві підзадачі, розмір кожної не перевищує n/2. Час роботи, описується нерівністю:
Тоді:
Середній випадок Математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах є
  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
операцій. Однак, у найгіршому випадку робить 
порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям.
. Тоді, рекурентне співвідношення для часу роботи, можна записати так:
.
— асимптотично найкращий час.
, тобто середній випадок ближчий до найкращого.