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

Зміст

Вступ

1. Сортування прямим злиттям

2. Природне злиття

3. Метод злиття впорядкованих серій

4. Багатофазне злиття

Висновки

Література

Додатки

Вступ

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

Проте рідко хто задумувався, як так швидко ви отримуєте цю інформацію? А все дуже просто, існує певна база даних, по ній проводиться пошук і вже по результатах вибірки робляться висновки. Зрозуміло, рядовому користувачу вникати в деталі неважливо, проте ми в своїй курсовій роботі зачепимо ряд питань.

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

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

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

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

З часом, ці методи були розбиті на декілька категорій, найбільш відомі серед яких, це прямі методи сортування масивів і послідовностей:

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

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

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

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

Та швидкі методи сортування:

- сортування алгоритмом Шелла;

- сортування алгоритмом Quick Sort;

- сортування алгоритмом Тree Sort;

- сортування алгоритмом Heap Sort.

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

Метою роботи є: Знайомство з теоретичним положенням, що стосуються методів сортування файлів, реалізація їх на мові програмування Turbo Pascal.

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

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