Інститут прикладного системного аналізу

з предмету: «Побудова та аналіз алгоритмів»

на тему: «Порівняння алгоритмів сортування»

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/2. Час роботи, описується нерівністю:

Математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах є

, тобто середній випадок ближчий до найкращого.

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: