на тему рефераты Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
на тему рефераты
на тему рефераты
МЕНЮ|
на тему рефераты
поиск
Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів

Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів

Міністерство освіти і науки України

Курсова робота на тему:

"Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів"

Зміст

Вступ

Розділ І. Алгоритми, методи сортування

Розділ ІІ. Прямі методи сортування масивів

2.1 Сортування прямим включенням

2.2 Сортування бінарним включенням

2.3 Сортування прямим вибором

2.4 Сортування прямим обміном

2.4.1 Метод "бульбашки"

2.4.2 Метод "камінця"

2.4.3 Метод шейкерного сортування

2.5 Порівняння прямих методів сортування масивів

Розділ ІІІ. Огляд функцій сортування із стандартної бібліотеки С++

Висновки

Література

Вступ

Мало яка людина зараз уявляє своє життя без комп'ютера та комп'ютерних технологій. Комп'ютери є скрізь, і в дома і на роботі, і в супермаркеті і на станції технічного обслуговування. Використання комп'ютерної техніки використовується у всіх областях життєдіяльності людини. Тому, різноманіття програмного забезпечення теж вражає.

Розробкою програмного забезпечення займається така галузь науки, як програмування. Саме на програмістах лежить відповідальність за створенні та реалізації різноманітних алгоритмів обробки певних задач. І інколи від вибору того чи іншого алгоритму залежить подальша доля програмного проекту.

Програмування містить цілу низку важливих внутрішніх задач. Однією з найбільш важливих таких задач для програмування є задача сортування. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Наприклад, потрібно відсортувати оцінки за екзамен від мінімальної оцінки до максимальної чи навпаки. Інший приклад - список неправильно вимовляємих слів, відсортований в алфавітному порядку. Особисті дані студентів можна відсортувати або по номеру студентського квитка, або в алфавітному порядку по імені студента. Всі ці задачі мають на меті впорядкування (сортування) за певною ознакою.

Взагалі, відомо, що в будь-якій сфері діяльності, що використовує комп'ютер для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування. Певна впорядкованість для них дуже важлива, адже користувачеві набагато легше працювати з даними, що мають певний порядок. Так, можна розташувати всі товари по назві або відомості про співробітників чи студентів за прізвищем або роком народження, тощо.

Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв'язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам'яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування включенням) не є дуже ефективними та більш простими у реалізації і наглядності.

Мета даної курсової роботи: знайомство з теоретичним положенням, що стосуються прямих алгоритмів сортування, аналіз їх швидкодії і кількості використаних операцій порівняння та обміну, реалізація цих алгоритмів на мові програмування С++.

У курсовій роботі ми детально розглянемо прямі методи сортування елементів масиву, проведемо їх порівняльний аналіз, вкажемо на їх позитиви і недоліки, що дасть змогу краще визначити ефективність і площину застосування.

При реалізації програм ми будемо використовувати мову програмування високого рівня С++. Методи сортування даних можна реалізовувати на багатьох мовах програмування як високого так і низького рівня. Проте, на нашу думку, найкраще на мові програмування фірми Borland - С++ або ж Turbo Pascal. В нашому випадку ми віддали перевагу першій.

С++ побудована на основі мови С. Вона зберігає основні типи даних, операції, синтаксис операторів та структуру програми мови С (про це свідчить сама назва мови: "C" та "++"). Водночас, це зовсім інша мова, яка ввела в практику програмування новий технологічний підхід - об'єктно-орієнтоване програмування. Введення в практику програмування об'єктно-орієнтованої парадигми дозволяє значно підвищити рівень технології створення програмних засобів, скоротити затрати на розробку програм, їх повторне використання, розширити інтелектуальні можливості ЕОМ.

Предмет дослідження: Прямі алгоритми сортування елементів масиву.

Об'єкт дослідження: Реалізація прямих методів сортування елементів масиву на С++ та використання їх на практиці.

Досягненням мети визначаються наступні завдання:

1. Вивчити літературу по темі "Прямі алгоритми сортування масивів" їх реалізація на С++;

2. Проаналізувати прямі методи сортування, їх практичне застосування;

3. Реалізувати на мові С++ прямі алгоритми сортування: сортування прямим включенням, бінарним включенням, прямим вибором, прями обміном;

4. Розробити закінчений програмний продукт по темі дослідження.

Розділ І. Алгоритми, методи сортування

Алгоритми - система правил, сформульована на зрозумілій виконавцеві мові, що визначає процес переходу від припустимих вихідних даних до деякого результату й має властивості масовості, кінцівки, визначеності, детермінованості.

Слово "алгоритм" походить від імені великого середньоазіатського вченого 8-9 ст. Аль-Хорезми (Хорезм - історична область на території сучасного Узбекистану). З математичних робіт Аль-Хорезми до нас дійшли тільки дві - алгебраїчна (від назви цієї книги народилося слово алгебра) і арифметична. Друга книга довгий час вважалася загубленої, але в 1857 у бібліотеці Кембриджського університету був знайдений її переклад на латинську мову. У ній описані чотири правила арифметичних дій, практично ті ж, що використаються й зараз. Перші рядки цієї книги були переведені так: "Сказав Алгоритми. Віддамо належну хвалу Богу, нашому вождеві й захисникові". Так ім'я Аль-Хорезми перейшло в Алгоритми, звідки й з'явилося слово алгоритм. Термін алгоритм вживався для позначення чотирьох арифметичних операцій, саме в такім значенні він і ввійшов у деякі європейські мови. Наприклад, в авторитетному словнику англійської мови Webster's New World Dictionary, виданому в 1957, слово алгоритм позначене позначкою "застаріле" і пояснюється як виконання арифметичних дій за допомогою арабських цифр.

Слово "алгоритм" знову стало вживаним з появою електронних обчислювальних машин для позначення сукупності дій, що становлять деякий процес. Тут мається на увазі не тільки процес рішення деякого математичного завдання, але й багато інших послідовних правил, що не мають відносини до математики, - всі ці правила є алгоритмами.

Аналогічно як існує алгоритм приготування борщу, існують алгоритми сортування масивів.

Способів сортування є дуже багато, ще більше є способів їх фізичної реалізації. Так, один і той самий метод можна реалізувати, спираючись на різні структури, методи і використання різних прийомів програмування. Тобто ми можемо використати як звичайний лінійний підхід до розв'язання задачі, так і процедурний, а можемо той самий алгоритм реалізувати з допомогою рекурсії.

Вибір алгоритму залежить від структури даних, що обробляються. У випадку сортування ця залежність настільки велика, що відповідні методи навіть були розбиті на дві групи - сортування масивів і сортування файлів (послідовностей). Іноді їх називають внутрішнім і зовнішнім і сортуванням, оскільки масиви зберігаються в швидкій внутрішній пам'яті (оперативній) із довільним доступом, а файли розміщуються в менш швидкій, проте більш об'ємній зовнішній пам'яті.

Метод сортування називається стійким, якщо в процесі впорядкування відносне розміщення елементів з рівними значеннями не міняється. Стійкість сортування часто буває бажаним, якщо йде мова про елементи, що вже впорядковані по деяких вторинних ключах (тобто ознаках), які не впливають на основний ключ.

Нехай маємо масив елементів довільного типу (тут і надалі ми будемо працювати із масивом цілих чисел int mas[1000], за необхідності його досить легко переробити в масив дійсних чисел, символів, чи рядків. Тобто універсальність алгоритмів сортування полягає в тому, що вони практично не залежать від типу елементів масиву). Даний масив містить 1001 елемент, елемент з індексом 0 ми будемо використовувати лише в окремих випадках, і працюватимемо лише із певною частиною масиву з індексами 1 . . . n, де n - кількість елементів масиву, що потрібно відсортувати. Аналогічно, ми будемо сортувати ці масиви по зростанню, що аж ніяк не обмежує загальності.

Алгоритми сортування окрім критерію економії пам'яті будуть класифікуватися по швидкості, тобто по часу їх роботи. Оскільки на різних типах ЕОМ одні і ті ж методи показуватимуть відмінні результати, то в якості міри ефективності алгоритму можуть бути прийняті числа: C - кількість необхідних порівнянь ключів; M - кількість перестановок елементів. Очевидно, що ці числа є функціями від кількості елементів в масиві N.

Методів сортування є досить багато, це прямі, та швидкі, які більш складні у реалізації але дають відмінні результати швидкості. Швидкі методи в основному реалізовані за рахунок введення додаткових конструкцій, як то дерева, стеки, черги.

До прямих методів належать:

- сортування прямим включенням;

- сортування бінарним включенням;

- сортування прямим вибором;

- сортування прямим обміном.

В основі прямих методів лежить повторення N етапів обробки масиву із зменшенням на кожному з них кількості порівнюваних елементів. Ефективність даних алгоритмів є величиною порядку O(N2). Саме тому, їх ще називають квадратичними методами сортування. Такі методи зручно використовувати на так званих "коротких" масивах.

Зрозуміло, що крім самих методів сортування існує ще більше способів їх реалізації, які в певних випадках прискорюють їх роботу, а в певних випадках їх пригальмовують. Так, для прикладу алгоритм сортування Шела можна реалізувати використовуючи рекурсивні запити, а можна і лінійним програмуванням. Для прикладу, обмін елементів масиву використовуючи операції віднімання та додавання відбувається в загальному швидше ніж введення тимчасової змінної із подальшим її переприсвоєнням.

Розділ ІІ. Прямі методи сортування масивів

2.1 Сортування прямим включенням

В основі розглядуваного методу лежить пошук для чергового елемента масиву відповідного місця у відсортованій частині із наступним включенням його в знайдену позицію. Таким чином елементи масиву умовно діляться на дві групи - вже "готову" послідовність mas[1], mas[2], … ,mas[i] та вихідну послідовність. На кожному етапі, починаючи з i=2 та збільшуючи i кожен раз на 1, із вихідної послідовності вибирається один елемент і вставляється в потрібне місце у вже впорядковану послідовність. Очевидно, що початкова ліва послідовність буде "готовою", оскільки одноелементний масив завжди впорядкований. Продовжуючи по аналогії, в кінці-кінців отримаємо впорядкований список, що містить всі елементи масиву, а новий список відповідно збільшиться. Для реалізації цього алгоритму можна використовувати інший масив, куди будуть добавлятися скопійовані в потрібне місце елементи другого масиву, а можна використовувати той же масив, адже зрозуміло, що один масив росте із тією ж швидкістю що і інший зменшується.

Даний алгоритм можна показати наочно наступним чином:

Розглянемо реалізацію даного алгоритму на нашому масиві. Нехай маємо 7 елементів масиву mas із індексами від 0 до 7. Елемент mas[0] відіграє роль бар'єра, що використовуватиметься нами для обміну елементами і спростить реалізацію алгоритму. Використання додаткового елемента в масиві - "бар'єра" mas[0]=x забезпечує гарантоване припинення процесу просіювання. Це дозволяє зменшити кількість логічних умов в заголовку циклу while до однієї, а кількість логічних операцій від 2i-1 до i на кожному етапі. Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індексу. На жаль, таке покращення ефективності по кількості порівнянь не зменшує об'єму перестановок елементів.

Елемент масиву mas[1], виділений, щоб підкреслити те, що навіть в вихідному стані цю область можна розглядати як невеликий, окремо-впорядкований масив. Фактично, робота алгоритму починається із другого елемента масиву mas[2], до "впорядкованого масиву", в якому тепер будуть знаходитися два елементи.

Страницы: 1, 2, 3



© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.