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

Размещено на http://www.allbest.ru/

• Реферат
• Курсова робота присвячена порівнянню загальних характеристик роботи різних методів сортування.
• СОРТУВАННЯ МЕТОДОМ БУЛЬБАШКИ, СОРТУВАННЯ МЕТОДОМ ШЕЛЛА, ШВИДКЕ СОРТУВАННЯ, СОРТУВАННЯ ВСТАВКАМИ, СОРТУВАННЯ ВИБОРОМ, СОРТУВАННЯ МЕТОДОМ ЗНАХОДЖЕННЯ МІНІМАЛЬНОГО ЕЛЕМЕНТА
• Зміст
• Вступ
• 1. Відомості про методи сортування
• 2. Алгоритми
• 2.1 Сортування методом бульбашки
• 2.2 Сортування методом Шелла
• 2.3 Швидке сортування
• 2.4 Сортування вибором
• 2.5 Сортування вставками
• 3. Інструкція користувача програми
• 3.1 Сортування методом бульбашки
• Висновки
• Перелік використаних джерел
• Додаток А
• Додаток Б
• Вступ
• В даний час обчислювальна техніка проникла практично в усі сфери людської діяльності. За допомогою ЕОМ можна вирішувати найрізноманітніші завдання. Але для того, щоб вирішити поставлену задачу, необхідно вказати послідовність дій, виконання яких приведе до необхідного результату, - скласти програму. Для зручності роботи з ЕОМ ця операція проводиться за допомогою мов програмування (високого або низького рівня).
• Один із широко використовуваних мов програмування - це Visual C + +, який можна використовувати для написання програм, що працюють в операційному середовищі Windows. На даний час однієї з найпоширеніших його версій є Microsoft Visual C + +, і середовище програмування Visual studio.Середовище програмування Visual studio дозволяє створювати тексти програм, компілювати їх, знаходити помилки і оперативно їх виправляти; компонувати програми з окремих частин, включаючи стандартні модулі, налагоджувати і виконувати налагоджену програму.
• Використовуючи перераховані можливості, можна створювати різні прикладні програми, наприклад, такі, як програма, написана при виконанні даної курсової роботи.

1. Відомості про методи сортування

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

Перегруповування заданої множини об'єктів в певному порядку називають сортуванням.

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

"Навіть якщо б сортування була майже марна, знайшлася б маса причин зайнятися нею! Винахідливі методи сортування говорять про те, що вона і сама по собі цікава як об'єкт дослідження." / Д. Кнут /

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

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

Сортування і пошук належать до числа найбільш поширених і добре вивчених задач. Вони використовуються майже в усіх програмах СУБД, в компіляторах, інтерпретатора, операційних системах. Мета сортування - прискорення пошуку даних. Розрізняють сортування масивів і сортування файлів (зовнішні сортування)

Сортування - впорядковування набору однотипних даних по зростанню або убуванню. Мета сортування - полегшити подальший пошук елементів у такому відсортованому масиві.

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

Алгоритми сортування класифікують на алгоритми сортування об'єктів з довільним доступом (масиви і дискові файли довільного доступу) та алгоритми сортувальні послідовні об'єкти (файли на стрічках і дисках).

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

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

Критерії оцінки алгоритму сортування:

Наскільки швидко алгоритм сортує інформацію в середньому?

На скільки швидко він працює у кращому і гіршому випадках?

Природно або неприродно він себе веде?

Переставляє він елементи з однаковими ключами?

Швидкість сортування визначається кількістю порівнянь і кількістю обмінів. Час раб. Залежить від кількості елементів експоненціально - прямі методи сортування; логарифмічно - поліпшені методи сортування. Природне поведінка - час роботи алгоритму мінімально для впорядкованого масиву і максимально для масиву з елементами в зворотному порядку.

Мірою ефективності алгоритмів сортування можна вважати C - число необхідних порівнянь і M - число пересилань. Гарні алгоритми сортування вимагають n * log2 (n) порівнянь (n - число сортованих елементів).

Найпростіші і очевидні методи називаються прямими і вимагають n2 порівнянь. Програми цих методів легкі для розуміння і короткі (самі програми також займають пам'ять). Недоліком прямих методів є велика кількість порівнянь і перестановок.

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

2. Алгоритми

2.1 Сортування методом бульбашки

Розташуємо масив зверху вниз, від нульового елемента - до останнього.

Ідея методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями (Рис. 5.1).

Рисунок 2.1 - Принцип роботи сортування методом бульбашки

Після нульового проходу по масиву "вгорі" виявляється самий "легкий" елемент - звідси аналогія з бульбашкою (Рис. 5.2). Наступний прохід робиться до другого зверху елемента, таким чином другий за величиною елемент піднімається на правильну позицію.

Робимо проходи по все зменшується нижній частині масиву до тих пір, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, так як послідовність упорядкована за зростанням.(Рис.2.2)

Середнє число порівнянь та обмінів мають квадратичний порядок зростання: Theta (n2), звідси можна зробити висновок, що алгоритм бульбашки дуже повільний і малоефективний.



Рисунок 2.2 - Результат нульового кроку сортування

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

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

Це означає, що всі пари розташовані в правильному порядку, так що масив вже відсортований. І продовжувати процес не має сенсу (особливо, якщо масив був відсортований з самого початку!).

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

Процес поліпшення можна продовжити, якщо запам'ятовувати не тільки сам факт обміну, але і індекс останнього обміну k. Дійсно: всі пари сусіди елементів з індексами, меншими k, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі k, замість того щоб рухатися до встановленої заздалегідь верхньої межі i.

Якісно інше поліпшення алгоритму можна отримати з наступного спостереження. Хоча легкий бульбашка знизу підніметься наверх за один прохід, важкі бульбашки опускаються зі мінімальною швидкістю: один крок за ітерацію. Так що масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 зажадає 5 проходів.

Щоб уникнути подібного ефекту, можна змінювати напрямок наступних один за іншим проходів. Одержаний алгоритм іноді називають "шейкер-сортуванням".

Наскільки описані зміни вплинули на ефективність методу? Середня кількість порівнянь, хоч і зменшилася, але залишається O (n2), в той час як число обмінів не помінялося взагалі ніяк. Середнє (воно ж найгірше) кількість операцій залишається квадратичним.

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

На практиці метод бульбашки, навіть з поліпшеннями, працює, на жаль, занадто повільно. А тому - майже не застосовується.

2.2 Сортування методом Шелла

Сортування Шелла є досить цікавою модифікацією алгоритму сортування простими вставками.

Розглянемо наступний алгоритм сортування масиву a [0] .. a [15]

Рисунок 2.3 - Початковий стан масиву а

1. Спочатку сортуємо простими вставками кожні 8 груп з 2-х елементів (a [0], a [8 [), (a [1], a [9]), ... , (а [7], a [15]) (Рис. 5.4).

Рисунок 2.4 - Схема роботи методу сортування Шелла

2. Потім сортуємо кожну з чотирьох груп по 4 елемента (a [0], a [4], a [8], a [12]), ..., (a [3], a [7], a [11] , a [15]) (Рис. 5.5).

Рисунок 2.5 - Другий шаг сортування

В нульової групи будуть елементи 4, 12, 13, 18, в першій - 3, 5, 8, 9 тощо.

3. Далі сортуємо 2 групи по 8 елементів, починаючи з (a [0], a [2], a [4], a [6], a [8], a [10], a [12], a [14] ) (Рис. 5.6).

Рисунок 2.6 - Сортування груп елементів

4. В кінці сортуємо вставками всі 16 елементів (Рис. 5.7).

Рисунок 2.7 - Результат сортування методом Шелла

Очевидно, лише останнє сортування необхідне, щоб розташувати всі елементи по своїх місцях. Так навіщо потрібні інші?

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

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

Використаний в прикладі набір ..., 8, 4, 2, 1 - непоганий вибір, особливо, коли кількість елементів - ступінь двійки.

При використанні таких приростів середня кількість операцій: O (n7 / 6), в гіршому випадку - порядку O (n4 / 3).

Звернемо увагу на те, що послідовність обчислюється в порядку, протилежному використовуваному: inc [0] = 1, inc [1] = 5, ... Формула дає спочатку менші числа, потім все більші і більші, у той час як відстань між сортованими елементами, навпаки, має зменшуватися. Тому масив приростів inc обчислюється перед запуском власне сортування до максимальної відстані між елементами, яке буде першим кроком в сортуванні Шелла. Потім його значення використовуються в зворотному порядку.

2.3 Швидке сортування

Опис алгоритму:

1. вибрати елемент, званий опорним.

2. порівняти всі інші елементи з опорним, на підставі порівняння розбити безліч на три - «менші опорного», «рівні» та «великі», розташувати їх у порядку менші-рівні-великі.

3. повторити рекурсивно для «менших» і «великих».

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

Алгоритм швидкого сортування використовує стратегію «розділяй і володарюй». Кроки алгоритму наступні:

1. Вибираємо в масиві деякий елемент, який будемо називати опорним елементом. З точки зору коректності алгоритму вибір опорного елемента байдужий. З точки зору підвищення ефективності алгоритму вибиратися повинна медіана, але без додаткових відомостей про сортованих даних її зазвичай неможливо отримати. Відомі стратегії: вибирати постійно один і той же елемент, наприклад, середній або останній по положенню; вибирати елемент з випадково вибраним індексом.

2. Операція поділу масиву: реорганізуємо масив таким чином, щоб всі елементи, менші або рівні опорному елементу, виявилися зліва від нього, а всі елементи, великі опорного - праворуч від нього. Звичайний алгоритм операції:

3. Два індексу - l і r, прирівнюються до мінімального і максимального індексу розділяється масиву відповідно.

4. Обчислюється індекс опорного елемента m.

5. Індекс l послідовно збільшується до тих пір, поки l-й елемент не перевищить опорний.

6. Індекс r послідовно зменшується до тих пір, поки r-й елемент не виявиться менше або дорівнює опорному.

7. Якщо r = l - знайдена середина масиву - операція поділу закінчена, обидва індекси вказують на опорний елемент.

8. Якщо l <r - знайдену пару елементів потрібно обміняти місцями і продовжити операцію поділу з тих значень l і r, які були досягнуті. Слід врахувати, що якщо яка-небудь кордон (l або r) дійшла до опорного елемента, то при обміні значення m змінюється на r-й або l-й елемент відповідно.

9. Рекурсивно упорядковуємо подмассіва, що лежать ліворуч і праворуч від опорного елемента.

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

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

QuickSort є істотно поліпшеним варіантом алгоритму сортування за допомогою прямого обміну (його варіанти відомі як «Бульбашкова сортування» та «Шейкерная сортування»), відомого, зокрема, своєї низькою ефективністю. Принципова відмінність полягає в тому, що після кожного проходу елементи діляться на дві незалежні групи. Цікавий факт: поліпшення самого неефективного прямого методу сортування дало в результаті ефективний покращений метод.

Кращий випадок. Для цього алгоритму найкращий випадок - якщо в кожній ітерації кожен з підмасивів ділився б на два рівних по величині масиву. В результаті кількість порівнянь, які робить швидкої сортуванням, було б дорівнює значенню рекурсивного вираження CN = 2CN / 2 + N, що в явному вираженні дає приблизно N lg N порівнянь. Це дало б найменший час сортування.

Середнє. Дає в середньому O (n log n) обмінів при упорядкуванні n елементів. В реальності саме така ситуація зазвичай має місце при випадковому порядку елементів і виборі опорного елемента з середини масиву або випадково.

На практиці (у випадку, коли обміни є більш витратною операцією, ніж порівняння) швидке сортування значно швидше, ніж інші алгоритми з оцінкою O (n lg n), через те, що внутрішній цикл алгоритму може бути ефективно реалізований майже на будь-архітектурі. 2CN / 2 покриває витрати по сортуванню двох отриманих підмасива; N - це вартість обробки кожного елемента, використовуючи один або інший вказівник. Відомо також, що приблизне значення цього виразу одно CN = N lg N.

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

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

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

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

Будемо будувати готову послідовність, починаючи з лівого кінця масиву. Алгоритм складається з n послідовних кроків, починаючи від нульового і закінчуючи (n-1)-му.

На i-му кроці вибираємо найменший з елементів a [i] ... a [n] і міняємо його місцями з a [i]. Послідовність кроків при n = 5 зображена на Рис. 5.8.

Рисунок 2.8 - Приклад сортування вибором

Незалежно від номера поточного кроку i, послідовність a [0] ... a [i] (виділена курсивом) є впорядкованою. Таким чином, на (n-1)-му кроці вся послідовність, крім a [n] виявляється відсортованої, а a [n] стоїть на останньому місці по праву: все менші елементи вже пішли вліво.

Для знаходження найменшого елемента з n + 1 ,що розглядаються,алгоритм робить n порівнянь. З урахуванням того, що кількість розглянутих на черговому кроці елементів зменшується на одиницю, загальна кількість операцій обчислюється за формулою (2.1):

(2.1)

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

Алгоритм не використовує додаткової пам'яті: всі операції відбуваються "на місці".

Розглянемо послідовність з трьох елементів, кожен з яких має два поля, а сортування йде за першою з них (Рис. 2.9).

Рисунок 2.9 - Сортування масивів з двома полями

Результат її сортування можна побачити вже після кроку 0, так як більше обмінів не буде. Порядок ключів 2a, 2b був змінений на 2b, 2a, так що метод нестійкий.

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

2.5 Сортування вставками

Сортування простими вставками в чомусь схожа на вищевикладені методи.

Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином на його початку "виростає" відсортована послідовність.

Однак у сортуванні бульбашкою або вибором можна було чітко заявити, що на i-му кроці елементи a [0] ... a [i] стоять на правильних місцях і нікуди більше не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a [0] ... a [i] впорядкована. При цьому по ходу алгоритму в неї будуть вставлятися (див. назву методу) все нові елементи.

Будемо розбирати алгоритм, розглядаючи його дії на i-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a [0] ... a [i] і невпорядковану a [i +1] ... a [n].

На наступному, (i +1)-м кожному кроці алгоритму беремо a [i +1] і вставляємо на потрібне місце в готову частину масиву.

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

В залежності від результату порівняння елемент або залишається на поточному місці (вставка завершена), або вони міняються місцями і процес повторюється (Рис. 5.10).

Рисунок 2.10 - Процес сортування вставками

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

Аналогічно сортуванні вибором, середнє, а також найгірше число порівнянь і пересилань оцінюються як Theta (n2), додаткова пам'ять при цьому не використовується.

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

Алгоритм можна злегка поліпшити. Зауважимо, що на кожному кроці внутрішнього циклу перевіряються 2 умови. Можна об'єднати з в одне, поставивши в початок масиву спеціальний сторожовий елемент. Він повинен бути свідомо менше всіх інших елементів масиву. Тоді при j = 0 буде свідомо вірно a [0] <= x. Цикл зупиниться на нульовому елементі, що й було метою умови j> = 0.

Таким чином, сортування відбуватиметься правильним чином, а у внутрішньому циклі стане на одне порівняння менше. З урахуванням того, що воно проводилося Theta (n2) раз, це - реальна перевага. Однак, відсортований масив буде не повний, так як з нього зникло перше число. Для закінчення сортування це число слід повернути назад, а потім вставити в відсортовану послідовність a [1] ... a [n] (Рис. 5.11).

Рисунок 2.11 - Закінчення процесу сортування

3. Інструкція користувача

3.1 Сортування методом Шелла

У 1959 році Д.Л.Шелл запропонував замість систематичного включення елемента з індексом i в підмасив попередніх йому елементів (цей спосіб суперечить принципу "балансування", чому і не дозволяє отримати ефективний алгоритм) включати цей елемент в підсписок, що містить елементи з індексами ih, i-2h, i-3h і т.д., де h - деяка натуральна постійна. Таким чином формується масив, в якому h-серії елементів, віддалених один від одного на відстань h, сортуються окремо:

Після того, як розсортовані непересічні h-серії, процес поновлюється з новим значенням h '<h. Попереднє сортування серій з відстанню h значно прискорює сортування серій з відстанню h '.

Доведено, що максимальна складність алгоритму Шелла становить O (n5 / 4). Так як

(3.1)

то цей вид сортування придатний для послідовностей, що мають приблизно до 70 тис. елементів.

3.1.1 Покращення

При виборі опорного елемента з даного діапазону випадковим чином гірший випадок стає дуже малоймовірним і очікуваний час виконання алгоритму сортування - O (n lg n).

Вибирати опорним елементом середній з трьох (першого, середнього і останнього елементів). Такий вибір також спрямований проти гіршого випадку.

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

Розбивати масив не на дві, а на три частини (див. Dual Pivot Quicksort).

3.1.2 Переваги

Один з найбільш швидкодіючих (на практиці) з алгоритмів внутрішнього сортування загального призначення.

Простий в реалізації.

Потребує лише додаткової пам'яті для своєї роботи. (Не покращений рекурсивний алгоритм у гіршому випадку пам'яті)

Добре поєднується з механізмами кешування і віртуальної пам'яті.

Існує ефективна модифікація (алгоритм Седжвіка) для сортування рядків - спочатку порівняння з опорним елементом тільки за нульовим символу рядка, далі застосування аналогічної сортування для «більшого» і «меншого» масивів теж за нульовим символу, і для «рівного» масиву по вже першого символу.

3.1.3 Недоліки

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

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

Нестійкий - якщо потрібна стійкість, доводиться розширювати ключ.

Розглянемо роботу процедури для масиву a [0] ... a [6] і опорного елемента p = a [3].

Рисунок 5.8 - Приклад роботи процедури сортування

3.2 Сортування вставками

У функцію InsertionSort передається масив A і довжина списку n. Розглянемо i-ий прохід (1 <i <n-1). Підсписок від A [0] до A [i-1] вже відсортований за зростанням. Як вставляється (TARGET) виберемо елемент A [i] і будемо просувати його до початку списку, порівнюючи з елементами A [i-1], A [i-2] і т.д. Перегляд закінчується на елементі A [j], який менше або дорівнює TARGET або знаходиться на початку списку (j = 0). У міру просування до початку списку кожний елемент зсувається вправо (A [j] = A [j-1]). Коли відповідне місце для A [i] буде знайдено, цей елемент вставляється в точку j.

Сортування вставками вимагає фіксованого числа проходів. На n-1 проходах вставляються елементи від A [1] до A [n-1]. На i-му проході вставки виробляються в підсписок A [0]-A [i] і вимагають в середньому i / 2 порівнянь. Загальне число порівнянь єдине:

(3.2)

На відміну від інших методів, сортування вставками не використовує обміни. Складність алгоритму вимірюється числом порівнянь і дорівнює O (n2). Найкращий випадок - коли початковий список вже відсортований. Тоді на i-му проході вставка здійснюється в точці A [i], а загальне число порівнянь одно n-1, тобто складність становить O (n). Найгірший випадок виникає, коли список відсортований за спаданням. Тоді кожна вставка відбувається в точці A [0] і вимагає i порівнянь. Загальне число порівнянь одно n (n-1) / 2, тобто складність становить O (n2).

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

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

Оцінимо часову складність даного методу, використовуючи в якості основної операції операцію порівняння.

Для пошуку мінімального елемента в кожному проході потрібно виконати: n-1, n-2, 1 операцій порівняння, тобто всього n (n-1) / 2 операцій порівняння. Отже, обчислювальна складність даного методу O (n2). Причому час сортування не залежить від вихідного порядку елементів.

Рисунок 3.1 - Алгоритм сортування вибором

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

Загальний аналіз ефективності «швидкої» сортування досить важкий. Буде краще показати її обчислювальну складність, підрахувавши число порівнянь при деяких ідеальних припущеннях. Припустимо, що n - ступінь двійки, n = 2k (k = log2n), а центральний елемент розташовується точно посередині кожного списку і розбиває його на два підсписки приблизно однакової довжини.

При першому скануванні проводиться n-1 порівнянь. В результаті створюються два підсписки розміром n / 2. На наступній фазі обробка кожного підсписки вимагає приблизно n / 2 порівнянь. Загальне число порівнянь на цій фазі дорівнює 2 (n / 2) = n. На наступній фазі обробляються чотири підсписки, що вимагає 4 (n / 4) порівнянь, і т.д. Зрештою процес розбиття припиняється після k проходів, коли вийшли підсписки містять по одному елементу. Загальне число порівнянь приблизно дорівнює n + 2 (n / 2) + 4 (n / 4) + ... + N (n / n) = n + n + ... + N = n * k = n * log2n

Для списку загального вигляду обчислювальна складність «швидкої» сортування дорівнює O (n log2 n). Ідеальний випадок, який ми тільки що розглянули, фактично виникає тоді, коли масив вже відсортований за зростанням. Тоді центральний елемент потрапляє точно в середину кожного підсписки.

Якщо масив відсортований за спаданням, то на першому проході центральний елемент виявляється на середині списку і змінюється місцями з кожним елементом як у першому, так і в другому підсписки. Результуючий список майже відсортований, алгоритм має складність порядку O (n log2n).(рис. 3.2.1)

Найгіршим сценарієм для «швидкої» сортування буде той, при якому центральний елемент весь час потрапляє в одноелементні подспісок, а всі інші елементи залишаються в другому підсписки. Це відбувається тоді, коли центральним завжди є найменший елемент. Розглянемо послідовність 3, 8, 1, 5, 9.

Рисунок 3.2.1?опис методу швидкого сортування

На першому проході проводиться n порівнянь, а більший подспісок містить n-1 елементів. На наступному проході цей подспісок вимагає n-1 порівнянь і дає подспісок з n-2 елементів і т.д. Загальне число порівнянь одно: n + n-1 + n-2 + ... + 2 = n (n +1) / 2 - 1

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

Алгоритм QuickSort вибирається за основу в більшості універсальних сортують утиліт. Якщо ви не можете змиритися з продуктивністю найгіршого випадку, використовуйте пірамідальну сортування - більш стійкий алгоритм, складність якого дорівнює O (n log2n) і залежить тільки від розміру списку.

3.4 Метод сортування бульбашкою

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

Сортування методом бульбашки займає 61,3 секунд.

Висновки

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

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

В даній курсовій роботі ми розглянули «елементарні» та більш складні, а точніше швидкі алгоритми сортування. Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба пам'ятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.

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

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

Перелік використаних джерел

1. Страуструп Б. Язык программирования С++. Часть 2. -- Киев: "ДиаСофт", 1993. -- 296 с

2. Х.М.Дейтел, П.Дж. Дейтел Как программировать на С++.- М.:ЗАО «Издательство БИНОМ», 2000 г. -- 1024 с.

3. Страуструп Б. Язык программирования С++. Часть 1. -- Киев: "ДиаСофт", 1993. -- 264 с.

4. Марченко А.Л. "C++. Бархатный путь" (избранные главы)

алгоритм сортування метод

Додаток А

#include "stdafx.h"

#include <iostream>

#include <stdlib.h>

#include <time.h>

using namespace std;

template <class T>

void bubbleSort (T a [], long size) {

long i, j;

T x;

for (i = 0; i <size; i ++) {// i - номер проходу

for (j = size-1; j> i; j --) {// внутрішній цикл проходу

if (a [j-1]> a [j]) {

x = a [j-1]; a [j-1] = a [j]; a [j] = x; }}}}

template <class T>

void shakerSort (T a [], long size) {

long j, k = size-1;

long lb = 1, ub = size-1; // межі невідсортованої частини масиву

T x;

do {

// Прохід знизу вгору

for (j = ub; j> 0; j --) {

if (a [j-1]> a [j]) {

x = a [j-1]; a [j-1] = a [j]; a [j] = x;

k = j;}}

lb = k +1;

// Прохід зверху вниз

for (j = 1; j <= ub; j ++) {

if (a [j-1]> a [j]) {

x = a [j-1]; a [j-1] = a [j]; a [j] = x;

k = j;}}

ub = k-1;

} while (lb <ub);

};

int increment (long inc [], long size) {

int p1, p2, p3, s;

p1 = p2 = p3 = 1;

s = -1;

do {

if (++s % 2) {

inc [s] = 8 * p1 - 6 * p2 + 1;

} else {

inc [s] = 9 * p1 - 9 * p3 + 1;

p2 *= 2;

p3 *= 2;

}

p1 *= 2;

} while (3 * inc [s] <size);

return s > 0? -- s: 0;

};

template <class T>

void shellSort (T a [], long size) {

long inc, i, j, seq [40];

int s;

// Обчислення послідовності збільшень

s = increment (seq, size);

while (s >= 0) {

// Сортування вставками з інкрементом inc []

inc = seq [s --];

for (i = inc; i < size; i ++) {

T temp = a [i];

for (j = i - inc; (j >= 0) && (a [j] > temp); j -= inc)

a [j + inc] = a [j];

a [j + inc] = temp;

}

}

}

/*

int increment (long inc [], long size) {

// Inc [] масив, в які заносяться інкремент

// Size розмірність цього масиву

int p1, p2, p3, s;

p1 = p2 = p3 = 1;

s = -1;

do {// заповнюємо масив елементів за формулою Роберта Седжвіка

if (++ s% 2) {

inc [s] = 8 * p1 - 6 * p2 + 1;

} else {

inc [s] = 9 * p1 - 9 * p3 + 1;

p2 *= 2;

p3 *= 2;}

p1 *= 2;

// Заповнюємо масив, поки поточна інкремента хоча б в 3 рази менше кількості елементів у масиві

} while (3 * inc [s] < size);

return s > 0? - s: 0;

};// повертаємо кількість елементів у масиві

*/

/*

template <class T>

void shellSort (T a [], long size)

{

long inc, i, j, seq [40];

int s = increment (seq, size);

while (s> = 0) {

inc = seq [s -];

for (i = inc; i <size; i ++) {

T temp = a [i];

for (j = i-inc; (j> = 0) && (a [j]> temp); j - = inc)

a [j + inc] = a [j];

a [j + inc] = temp;

}

}

}

*/

template <class T>

void selectSort (T a [], long size) {

long i, j, k;

T x;

for (i = 0; i <size; i ++) {// i - номер поточного кроку

k = i; x = a [i];

for (j = i +1; j <size; j ++) // цикл вибору найменшого елемента

if (a [j] <x) {

k = j; x = a [j]; // k - індекс найменшого елемента

}

a [k] = a [i]; a [i] = x;}}

template <class T>

void insertSort (T a [], long size) {

T x;

long i, j;

for (i = 0; i <size; i ++) {// цикл проходів, i - номер проходу

x = a [i];

// Пошук місця елемента в готовій послідовності

for (j = i-1; j >= 0 && a [j]> x; j --)

a [j +1] = a [j]; // зрушуємо елемент направо, поки не дійшли

// Місце знайдено, вставити елемент

a [j +1] = x;}}

/*

template <class T>

inline void insertSortGuarded (T a [], long size) {

T x;

long i, j;

T backup = a [0]; // зберегти старий перший елемент

setMin (a [0]); // замінити на мінімальний

// Відсортувати масив

for (i = 1; i <size; i ++) {

x = a [i];

for (j = i-1; a [j]> x; j -)

a [j +1] = a [j];

a [j +1] = x;}

// Вставити backup на правильне місце

for (j = 1; j <size && a [j] <backup; j ++)

a [j-1] = a [j];

// Вставка елемента

a [j-1] = backup;}

*/

int main ()

{

int size;

cout << "Enter size: ";

cin >> size;

int * mass0 = new int [10];

int * mass1 = new int [10];

int * mass2 = new int [10];

int * mass3 = new int [10];

int * mass4 = new int [10];

srand (time (NULL));

for (int i = 0; i < 10; i ++)

mass0 [i] = mass1 [i] = mass2 [i] = mass3 [i] = mass4 [i] =rand () % 1000;

for (int i = 0; i < 10; i ++)

cout << mass0 [i] << ' ';

cout << endl << endl;

bubbleSort (mass0, 10);

shakerSort (mass1, 10);

shellSort (mass2, 10);

selectSort (mass3, 10);

insertSort (mass4, 10);

for (int i = 0; i < 10; i ++)

cout << mass0 [i] << ' ';

cout << endl << endl;

for (int i = 0; i < 10; i ++)

cout << mass1 [i] << ' ';

cout << endl << endl;

for (int i = 0; i < 10; i ++)

cout << mass2 [i] << ' ';

cout << endl << endl;

for (int i = 0; i <10; i ++)

cout << mass3 [i] << ' ';

cout << endl << endl;

for (int i = 0; i < 10; i ++)

cout << mass4 [i] << ' ';

cout << endl << endl;

delete [] mass0;

delete [] mass1;

delete [] mass2;

delete [] mass3;

delete [] mass4;

system ("pause");

return 0;

}

Додаток Б

Размещено на Allbest.ru

...