РЕФЕРАТ
Пояснювальна записка: 38с., 14 рис.,3 формули, 2 додатки, 4 джерела.
Курсова робота присвячена порівнянню загальних характеристик роботи різних методів сортування.
СОРТУВАННЯ МЕТОДОМ БУЛЬБАШКИ, СОРТУВАННЯ МЕТОДОМ ШЕЛЛА, ШВИДКЕ СОРТУВАННЯ, СОРТУВАННЯ ВСТАВКАМИ, СОРТУВАННЯ ВИБОРОМ, СОРТУВАННЯ МЕТОДОМ ЗНАХОДЖЕННЯ МІНІМАЛЬНОГО ЕЛЕМЕНТА
РЕФЕРАТ
Обьяснительная записка: 38с., 3рис., 2 приложения, 4 источника.
Курсовая работа посвящена сравнению общих характеристик работы разных методов сортировки.
СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА, СОРТИРОВКА МЕТОДОМ ШЕЛЛА, БЫСТРАЯ СОРТИРОВКА, СОРТИРОВКА ВСТАВКАМИ, СОРТИРОВКА ВЫБОРОМ, СОРТИРОВКА МЕТОДОМ НАХОЖДЕНИЯ МИНИМАЛЬНОГО ЭЛЕМЕНТА .
ЗМІСТ
ВСТУП
В даний час обчислювальна техніка проникла практично в усі сфери людської діяльності. За допомогою ЕОМ можна вирішувати найрізноманітніші завдання. Але для того, щоб вирішити поставлену задачу, необхідно вказати послідовність дій, виконання яких приведе до необхідного результату, - скласти програму. Для зручності роботи з ЕОМ ця операція проводиться за допомогою мов програмування (високого або низького рівня).
Один із широко використовуваних мов програмування - це Visual C + +, який можна використовувати для написання програм, що працюють в операційному середовищі Windows. На даний час однієї з найпоширеніших його версій є Microsoft Visual C + +, і середовище програмування Visual studio.Середовище програмування Visual studio дозволяє створювати тексти програм, компілювати їх, знаходити помилки і оперативно їх виправляти; компонувати програми з окремих частин, включаючи стандартні модулі, налагоджувати і виконувати налагоджену програму.
Використовуючи перераховані можливості, можна створювати різні прикладні програми, наприклад, такі, як програма, написана при виконанні даної курсової роботи.
1.Відомості про методи сортування
Для вирішення багатьох завдань зручно спочатку упорядкувати дані за певною ознакою, так можна прискорити пошук деякого об'єкту. Наприклад, в преферансі гравці розкладають карти по мастям і за значенням. Так легше визначити, яких карт не вистачає. Або візьмемо будь енциклопедичний словник - статті в ньому впорядковані в алфавітному порядку.
Перегруповування заданої множини об'єктів в певному порядку називають сортуванням.
Чому сортування приділяється велика увага? Ви це зрозумієте, прочитавши цитати двох великих людей.
"Навіть якщо б сортування була майже марна, знайшлася б маса причин зайнятися нею! Винахідливі методи сортування говорять про те, що вона і сама по собі цікава як об'єкт дослідження." / Д. Кнут /
"Складається враження, що можна побудувати цілий курс програмування, вибираючи приклади тільки із завдань сортування." / Н. Вірт /
Відмінною особливістю сортування є та обставина, що ефективність алгоритмів, що реалізують її, прямо пропорційна складності розуміння цього алгоритму. Іншими словами, чим легше для розуміння метод сортування масиву, тим нижче його ефективність.
Сортування і пошук належать до числа найбільш поширених і добре вивчених задач. Вони використовуються майже в усіх програмах СУБД, в компіляторах, інтерпретатора, операційних системах. Мета сортування - прискорення пошуку даних. Розрізняють сортування масивів і сортування файлів (зовнішні сортування)
Сортування - впорядковування набору однотипних даних по зростанню або убуванню. Мета сортування - полегшити подальший пошук елементів у такому відсортованому масиві.
Qsort сортує тільки масиви в пам'яті. Вона не може сортувати дані в пов'язаних списках. Ця функція параметрезованих, тому вона може обробляти великий спектр даних, але через це вона може працювати повільніше, ніж функція нарахована на конкретний тип даних.
Алгоритми сортування класифікують на алгоритми сортування об'єктів з довільним доступом (масиви і дискові файли довільного доступу) та алгоритми сортувальні послідовні об'єкти (файли на стрічках і дисках).
При сортуванні даних використовується тільки частина даних - ключ, який визначає порядок елементів. Тобто порівняння відбувається по ключу, а в преремещеніі бере участь вся структура даних. Далі все приклади стосуватимуться масиву int, в якому ключ і дані збігаються.
Основна умова: метод сортування масивів повинен економно використовувати доступну пам'ять. Це передбачає, що перестановки, що призводять елементи в порядок, повинні виконуватися на тому ж місці, тобто методи, в яких елементи з масиву a передаються в результуючий масив b, представляють істотно менший інтерес. Обмеживши критерієм економії пам'яті вибір потрібного методу серед безлічі можливих, ми будемо класифікувати методи по їх економічності, тобто по часу їх роботи.
Критерії оцінки алгоритму сортування:
Наскільки швидко алгоритм сортує інформацію в середньому?
На скільки швидко він працює у кращому і гіршому випадках?
Природно або неприродно він себе веде?
Переставляє він елементи з однаковими ключами?
Швидкість сортування визначається кількістю порівнянь і кількістю обмінів. Час раб. Залежить від кількості елементів експоненціально - прямі методи сортування; логарифмічно - поліпшені методи сортування. Природне поведінка - час роботи алгоритму мінімально для впорядкованого масиву і максимально для масиву з елементами в зворотному порядку.
Мірою ефективності алгоритмів сортування можна вважати C - число необхідних порівнянь і M - число пересилань. Гарні алгоритми сортування вимагають n * log2 (n) порівнянь (n - число сортованих елементів).
Найпростіші і очевидні методи називаються прямими і вимагають n2 порівнянь. Програми цих методів легкі для розуміння і короткі (самі програми також займають пам'ять). Недоліком прямих методів є велика кількість порівнянь і перестановок.
Ускладнені методи вимагають невеликого числа операцій, але ці операції зазвичай самі складніші, і тому для невеликих масивів прямі методи виявляються краще, хоча для великих масивів їх застосовувати, звичайно, не слід.