Методи внутрішнього сортування Обмінна сортування Порівняння з іншими методами сортування

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Курсова робота

з дисципліни «Алгоритмічне забезпечення ЕВС»

на тему «Методи внутрішнього сортування. Обмінна сортування.

Порівняння з іншими методами сортування »

20 1910

Зміст

Введення

1. Сортування включенням

2. Сортування Шелла

3. Обмінна сортування

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

5. Сортування поділом

6. Порівняння методів

Висновок

Додаток

Література

Введення

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

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

1. Сортування включенням

Одним з найбільш простих і природних методів внутрішнього сортування є сортування з простими включеннями. Ідея алгоритму дуже проста. Нехай є масив ключів a [1], a [2], ..., a [n]. Для кожного елемента масиву, починаючи з другого, проводиться порівняння з елементами з меншим індексом (елемент a [i] послідовно порівнюється з елементами a [i-1], a [i-2] ...) і до тих пір, поки для чергового елемента a [j] виконується співвідношення a [j]> a [i], a [i] і a [j] міняються місцями. Якщо вдається зустріти такий елемент a [j], що a [j] <= a [i], або якщо досягнуто нижня межа масиву, відбувається перехід до обробки елемента a [i +1] (поки не буде досягнута верхня межа масиву).

Легко бачити, що в кращому випадку (коли масив вже впорядкований) для виконання алгоритму з масивом з n елементів буде потрібно n-1 порівняння і 0 пересилань. У найгіршому випадку (коли масив упорядковано в зворотному порядку) буде потрібно n? (N-1) / 2 порівнянь і стільки ж пересилань. Таким чином, можна оцінювати складність методу простих включень як O (n2).

Можна скоротити число порівнянь, які застосовуються в методі простих включень, якщо скористатися тим фактом, що при обробці елемента a [i] масиву елементи a [1], a [2], ..., a [i-1] вже упорядковані, і скористатися для пошуку елемента, з яким повинна бути проведена перестановка, методом двійкового поділу. У цьому випадку оцінка числа необхідних порівнянь стає O (n? Log n). Зауважимо, що оскільки при виконанні перестановки потрібно сдвіжка на один елемент декількох елементів, то оцінка числа пересилань залишається O (n2).

Таблиця 1.1 Приклад сортування методом простого включення

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок 1	8 23 5 65 44 33 1 6
Крок 2	8 5 23 65 44 33 1 6 5 8 23 65 44 33 1 6
Крок 3	5 8 23 65 44 33 1 6
Крок 4	5 8 23 44 65 33 1 6
Крок 5	5 8 23 44 33 65 1 6 5 8 23 33 44 65 1 6
Крок 6	5 8 23 33 44 1 65 6 5 8 23 33 1 44 65 6 5 8 23 1 33 44 65 6 5 8 1 23 33 44 65 6 5 1 8 23 33 44 65 6 1 5 8 23 33 44 65 6
Крок 7	1 5 8 23 33 44 6 65 1 5 8 23 33 6 44 65 1 5 8 23 6 33 44 65 1 5 8 6 23 33 44 65 1 5 6 8 23 33 44 65

2. Сортування Шелла

Подальшим розвитком методу сортування з включеннями є сортування методом Шелла, Віфесда по-іншому сортуванням включеннями з зменшуваним відстанню. Ми не будемо описувати алгоритм у загальному вигляді, а обмежимося випадком, коли число елементів в сортованому масиві є ступенем числа 2. Для масиву з 2n елементами алгоритм працює наступним чином. На першій фазі проводиться сортування включенням всіх пар елементів масиву, відстань між якими є 2 (n-1). На другій фазі виробляється сортування включенням елементів отриманого масиву, відстань між якими є 2 (n-2). І так далі, поки ми не дійдемо до фази з відстанню між елементами, що дорівнює одиниці, і не виконаємо завершальну сортування із включеннями. Застосування методу Шелла до масиву, що використовується в наших прикладах, показано в таблиці 2.2.

Таблиця 1. 2. Приклад сортування методом Шелл

У загальному випадку алгоритм Шелла природно переформуліруется для заданої послідовності з t відстаней між елементами h1, h2, ..., ht, для яких виконуються умови h1 = 1 і h (i +1) <hi. Дональд Кнут показав, що при правильно підібраних t і h складність алгоритму Шелла є O (n (1.2)), що істотно менше складності простих алгоритмів сортування.

3. Обмінна сортування

Проста обмінна сортування (у просторіччі звана "методом бульбашки") для масиву a [1], a [2], ..., a [n] працює наступним чином. Починаючи з кінця масиву порівнюються два сусідні елементи (a [n] і a [n-1]). Якщо виконується умова a [n-1]> a [n], то значення елементів міняються місцями. Процес триває для a [n-1] і a [n-2] і т.д., поки не буде вироблено порівняння a [2] і a [1]. Зрозуміло, що після цього на місці a [1] виявиться елемент масиву з найменшим значенням. На другому кроці процес повторюється, але останніми порівнюються a [3] і a [2]. І так далі. На останньому кроці будуть порівнюватися тільки поточні значення a [n] і a [n-1]. Зрозуміла аналогія з бульбашкою, оскільки найменші елементи (самі "легкі") поступово "спливають" до верхньої межі масиву. Приклад сортування методом бульбашки показано у таблиці 2.3.

Таблиця 1. 3. Приклад сортування методом Бульбашки

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок 1	8 23 5 65 44 33 1 6 8 23 5 65 44 1 33 6 8 23 5 65 1 44 33 6 8 23 5 1 65 44 33 6 8 23 1 5 65 44 33 6 8 1 23 5 65 44 33 6 1 8 23 5 65 44 33 6
Крок 2	1 8 23 5 65 44 6 33 1 8 23 5 65 6 44 33 1 8 23 5 6 65 44 33 1 8 23 5 6 65 44 33 1 8 5 23 6 65 44 33 1 5 8 23 6 65 44 33
Крок 3	1 5 8 23 6 65 33 44 1 5 8 23 6 33 65 44 1 5 8 23 6 33 65 44 1 5 8 6 23 33 65 44 1 5 6 8 23 33 65 44
Крок 4	1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Крок 5	1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Крок 6	1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Крок 7	1 5 6 8 23 33 44 65

Для методу простий обмінної сортування потрібно число порівнянь n ^x (n-1) / 2, мінімальне число пересилань 0, а середнє і максимальне число пересилань - O (n ^2).

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

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

Таблиця 4. Приклад шейкерной сортування

Шейкерная сортування дозволяє скоротити число порівнянь (за оцінкою Кнута середнім числом порівнянь є (n2 - n? (Const + ln n)), хоча порядком оцінки як і раніше залишається n2. Число ж пересилань, взагалі кажучи, не змінюється. Шейкерную сортування рекомендується використовувати в тих випадках, коли відомо, що масив "майже впорядкований".

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

Під час сортування масиву a [1], a [2], ..., a [n] методом простого вибору серед всіх елементів знаходиться елемент з найменшим значенням a [i], і a [1] і a [i] обмінюються значеннями. Потім цей процес повторюється для отримуваних подмассивов a [2], a [3], ..., a [n], ... a [j], a [j +1], ..., a [n] до тих пір, поки ми не дійдемо до подмассивов a [n], що містить до цього моменту найбільшого значення. Робота алгоритму ілюструється прикладом в таблиці 2.5.

Таблиця 5. Приклад сортування простим вибором

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок 1	1 23 5 65 44 33 8 6
Крок 2	1 5 23 65 44 33 8 6
Крок 3	1 5 6 65 44 33 8 23
Крок 4	1 5 6 8 44 33 65 23
Крок 5	1 5 6 8 33 44 65 23
Крок 6	1 5 6 8 23 44 65 33
Крок 7	1 5 6 8 23 33 65 44
Крок 8	1 5 6 8 23 33 44 65

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

5. Сортування поділом (Quicksort)

Метод сортування поділом був запропонований Чарльзом Хоаром (він любить називати себе Тоні) в 1962 р. Цей метод є розвитком методу простого обміну і настільки ефективний, що його стали називати "методом швидкого сортування - Quicksort".

Основна ідея алгоритму полягає в тому, що випадковим чином вибирається певний елемент масиву x, після чого масив проглядається зліва, поки не зустрінеться елемент a [i] такий, що a [i]> x, а потім масив проглядається праворуч, поки не зустрінеться елемент a [j] такий, що a [j] <x. Ці два елементи міняються місцями, і процес перегляду, порівняння та обміну триває, поки ми не дійдемо до елемента x. У результаті масив виявиться розбитим на дві частини - ліву, в якій значення ключів будуть менше x, і праву зі значеннями ключів, великими x. Далі процес рекурсивно продовжується для лівої і правої частин масиву до тих пір, поки кожна частина не буде містити в точності один елемент. Зрозуміло, що як завжди, рекурсію можна замінити итерациями, якщо запам'ятовувати відповідні індекси масиву. Простежимо цей процес на прикладі нашого стандартного масиву (таблиця 2.6).

Таблиця 6. Приклад швидкого сортування

Початковий стан масиву	8 23 травня 1965 | 44 | 33 6 січня
Крок 1 (в якості x вибирається a [5])	|--------| 8 23 5 6 44 33 1 65 |---| 8 23 5 6 1 33 44 65
Крок 2 (у підмасиві a [1], a [5] в якості x вибирається a [3])	Серпні 1923 | 5 | 1 червня 1933 44 65 |--------| 1 23 5 6 8 33 44 65 | - | 1 5 23 6 8 33 44 65
Крок 3 (у підмасиві a [3], a [5] в якості x вибирається a [4])	1 Травня 1923 | 6 | 8 33 44 65 |----| 1 5 8 6 23 33 44 65
Крок 4 (у підмасиві a [3], a [4] вибирається a [4])	1 5 8 | 6 | 23 33 44 65 | - | 1 5 6 8 23 33 44 65

Алгоритм недарма називається швидкої сортуванням, оскільки для нього оцінкою числа порівнянь і обмінів є O (n? Log n). Насправді, в більшості утиліт, що виконують сортування масивів, використовується саме цей алгоритм.

6. Порівняння методів

Для порівняння методів сортування була написана програма, що дозволяє виконати сортування п'ятьма способами, за зростанням або спаданням. Заповнення масиву проводиться випадковими даними.

Рис 1. Інтерфейс програми.

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

Таблиця 7

На підставі даних таблиці були побудовані графіки.

Рис 2. Залежність числа перестановок від розміру масиву

Рис 3. Залежність числа порівнянь від розміру масиву.

Висновки

За результатами замірів продуктивності методів можна зробити наступні висновки:

1. Найбільш універсальним методом, є метод швидкого сортування («QuickSort»), він показує стабільно високі результати на будь-яких розмірах масивів. На другому місці знаходиться метод Шелла. Його використання може бути обгрунтовано більше простим алгоритмом з точки зору програміста.

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

3. При використанні невеликих масивів даних немає великої різниці в швидкості між методами сортування, тому доцільніше застосовувати метод Бульбашки або метод вставок.

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

Додаток

Блок схеми.

Обмінна сортування.

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

Сортування вставкою.