Навигация
Порівняльна характеристика швидкодії деяких швидких алгоритмів сортування
43832
знака
1
таблица
0
изображений
2.5 Порівняльна характеристика швидкодії деяких швидких алгоритмів сортування
Щоб порівняти швидкодію певних алгоритмів сортування, зокрема Quick_Sort, Heap_Sort, Shell_Sort, ми створили одновимірний масив із елементів n=50000, типу integer. При цьому розглядалися різні варіанти масиву А(n). А саме, коли вихідний масив А(n) вже є відсортований за зростанням (за спаданням), коли всі члени масиву А(n) рівні, а також, коли елементи масиву генеруються випадковим чином. За отриманими результатами ми подували таблицю, яка дає змогу проаналізувати дані, і виявити кращі алгоритми сортування у різних випадках.
| № | Алгоритм сортування | Сортування відсортованого масиву по зростанню (мс) | Сортування по зростанню відсортованого масиву по спаданню (мс) | Сортування масиву, всі елементи однакові (мс) | Сортування масиву генерованого випадковим чином (мс) |
| 1 | Quick_Sort | 17000 | 11000 | 14 | 25 |
| 2 | Heap_Sort | 40 | 40 | 8 | 55 |
| 3 | Shell_Sort | 40 | 50 | 46 | 77 |
Висновки
Отже, ми розглянули як працюють швидкі алгоритми сортування іь спробували визначити їх складність.
Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба пам’ятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.
Так, алгоритм сортування деревом, хоча й працює однаково на всіх входах (так, що його складність в гіршому випадку співпадає зі складністю в середньому), але цей алгоритм має і досить суттєвий недолік: для нього потрібна додаткова пам’ять розміром 2n-1.
Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортування, можна зазначити, що цей алгоритм ефективніший ніж попередній, адже він сортує "на місці" , тобто він не потребує додаткових масивів. Крім того, цей алгоритм (" з точністю до мультиплікативної константи" (4,74)) оптимальний: його складність співпадає з нижньою оцінкою задачі, тобто за критеріями C(n) та M(n) він має складність O(n log2 n), але містить складний елемент в умові. Тобто, в умові A[left] має бути строго менше ніж x , а A[right] - строго більше за x. Якщо ж замість "строго більше" та "строго менше" поставити знаки, що позначають "більше, або дорівнює" та "менше, або дорівнює", то індекси left і right пробіжать увесь масив і побіжать далі. Вийти з цієї ситуації можна було б шляхом ускладнення умов продовження перегляду, але це б погіршило ефективність програми.
В нашій роботі ми розглянули деякі швидкі алгоритми сортування та їх реалізацію мовою Pascal, виконуючи курсову роботу ми реалізували програмно не лише використання швидких методів сортування, а і прямих, дослідили не лише переваги таких алгоритмів, ефективність їх використання, але й визначили деякі недоліки окремих алгоритмів, що заважають вживати їх для вирішення першої ліпшої задачі сортування. Програма, в якій міститься реалізація та демонстрація наявних прямих методів сортування називається Prjami.pas, а швидкі - Shvud.pas.
Отже, головною задачею, яку має вирішити людина, яка повинна розв’язати задачу сортування – це визначення як позитивних, так і усіх негативних характеристик різних алгоритмів сортування, передбачення кінцевого результату. До того ж , треба враховувати головне – чи , можливо, цю задачу задовольнить один з класичних простих алгоритмів сортування.
Література
1. Абрамов С. А., Зима Е. В. Начала программирования на языке Pascal. - М.: Наука, 1987.
2. Абрамов В. Г. Введение в язык Pascal: Учебное пособие для студентов вузов по специальности Прикладная математика. – М.: Наука, 1988.
3. Власик А.П. Практикум з програмування в середовищі Turbo Pascal. Ч 1.- Рівне: НУВГП, 2005. – 179 с.
4. Джонс Ж., Харроу К. Решение задач в системе Турбо-Паскаль/ Перевод с английского Улановой, Широкого. – М.: Финансы и статистика, 1991.
5. Зуев Е. А. Язык программирования Турбо Паскаль 6.0, 7.0. – М.: Радио и связь, 1993.
6. Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. – М.:Издательский дом "Вильямс", 2000. – 750 с.
7. Культин Н. Б. Программирование в TurboPascal 7.0 и Delphi. - Санкт- петербург,1999.
8. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. Херсон, 1997.
9. Перминов О. Н. Программирование на языке Паскаль. – М.: Радио и связь, 1988.
10. Перминов О. Н. Язык программирования Pascal. – М.: Радио и свіязь,1989.
11. Турбо Паскаль 7.0 Издание 10-е стереотипное. – Санкт-Петербург: "Печатный Двор", 1999.
12. Фаронов В. В. TurboPascal 7.0 . Начальный курс. – М.: "Нолидж", 2000.
13. Turbo Pascal – Издательская група К.: ВНV, 2000.
Похожие работы
... Висновки по розділу 3 У даному розділі диплома була розроблена автоматизована інформаційна система розрахунку прибутку на гірничо-збагачувальному підприємстві. Дана система була розроблена для підвищення ефективності роботи підприємства. В основу алгоритмів обробки даних покладені методи математичної статистики й оптимізаційні моделі. Для проектування і реалізації автоматизованої інформаційної ...
... стимулювати учнів до нових зусиль у роботі, до самостійного переборення труднощів – це істотна ознака майстерності вчителя. Розділ 2. Технологія організації самостійної роботи учнів на уроках у початковій школі 2.1 Дидактичні умови організації самостійної роботи молодших школярів Визначаючи дидактико-методичні підходи до організації самостійної роботи учнів, ми враховували творчі надбання ...
... · пошуковий механізм, який користувачі використовують як інтерфейс для взаємодії з базою даних. Засоби пошуку типу агентів, павуків, кроулерів і роботів використовуються для збору інформації про документи, які знаходяться в мережі Інтернет. Це спеціальні програми, які займаються пошуком сторінок в мережі, збирають гіпертекстові посилання з цих сторінок і автоматично індексують інформацію, яку ...
... Чарка, стакан 4 320 2 80 400 Столові прибори (комплект) 4 320 2 80 400 Далі наведемо характеристику посуду, який будуть використовувати в комплексному закладі ресторанного господарства (табл. 2.8–2.11). Таблиця 2.8. Характеристика та призначення класичного вітчизняного порцелянового та фаянсового посуду Найменування Розміри, мм Місткість, см3, порцій Призначення ...
0 комментариев