Курсова робота на тему: «МЕТОДИ ШВИДКОГО СОРТУВАННЯ»

Зміст

Вступ    3

1. Сортування    4

2. Пірамідальне сортування    10

3. Метод швидкого сортування.    16

4. Бінарне дерево пошуку.    20

5. Сортування гребінцем.    22

Висновки    25

Література    26

Вступ

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

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

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

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

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

1. Сортування.

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

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

Сортування застосовується в усіх без винятку областях програмування, будь-то бази даних чи математичні програми.

Практично кожен алгоритм сортування можна розбити на три частини:

– порівняння, що визначає впорядкованість пари елементів;

– перестановку, що змінює місцями пару елементів;

– власне сортуючий алгоритм, що здійснює порівняння і перестановку елементів доти, поки всі елементи множини не будуть впорядковані.

    Подібними властивостями володіють і ті п’ять алгоритмів сортування, що розглянуті нижче. Вони відібрані з безлічі алгоритмів, тому що:

по-перше, найбільш часто використовуються;

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

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

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

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

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

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

Як було зазначено раніше, у деяких програмах сортування краще використовувати прості алгоритми. Програми сортування часто використовуються тільки один раз (або кілька разів). Якщо кількість елементів, які потрібно відсортувати не велика (скажімо менше ніж 500 елементів), то можливо, що використання простого алгоритму буде більш ефективним, чим розробка і налагодження складного алгоритму. Елементарні методи завжди придатні для маленьких файлів (скажімо менших чим 50 елементів); малоймовірно, що складний алгоритм було б розумно використовувати для таких файлів, якщо звичайно не потрібно сортувати велику кількість таких файлів.

Як правило, елементарні методи, що ми будемо обговорювати, роблять приблизно N2 операції для сортування N довільно узятих елементів. Якщо N досить маленьке, то це може і не бути проблемою, і якщо елементи розподілені не довільним чином, то ці алгоритми можуть працювати навіть швидше, ніж складні. Однак варто запам’ятати те, що ці алгоритми не слід використовувати для великих, довільно впорядкованих файлів.

Перед тим, як розглядати який-небудь конкретний алгоритм, було б корисно вивчити термінологію і деякі основні положення про алгоритми сортування.

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

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Metody Schvydk Sort (152.5 KiB, Завантажень: 6)

Сторінка: 1 2 3 4 5
завантаження...
WordPress: 23.69MB | MySQL:26 | 0,377sec