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

Зміст

Вступ

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

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

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

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

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

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

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

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

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

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

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

Висновки

Література

Вступ

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

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

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

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

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

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

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

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

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

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

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

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

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--