Лекція 6 (6):

Тема: Алгоритм сортування масивів: Однобічний метод – мінімакса. Метод «бульбашки». Метод ставлення. Алгоритм «швидкого сортування» з використанням рекурсії.

План:

1. Поняття сортування (Методи внутрішньою і зовнішньою) сортування

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

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

4. Метод бульбашки

5. Шейкерне сортування

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

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

8. Сортування розділенням (Quicksort)

9. Сортування за допомогою дерева (Heapsort)

10. Сортування із злиттям.

Сортування є процесом впорядкування елементів в масиві в порядку зростання або убування їх значень. Наприклад, масив X з n елементів буде відсортований в порядку зростання значень його елементів, якщо X1 _ X2 _..._ Xn, і в порядку убування, якщо X1 _ X2 _ ... _ Xn.

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

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

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

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

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

Взаємне розташування рівних елементів з ключем 1 і додатковими полями "a", "b", "c" залишилося тим самим: елемент з полем "a", потім - з "b", потім - з "c".

Взаємне розташування рівних елементів з ключем 1 і додатковими полями "a", "b", "c" змінилося.

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

Ще однією важливою властивістю алгоритму є його сфера застосування. Тут основних позицій дві:

• внутрішні сортування працюють з даним в оперативній пам'яті з довільним доступом;

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

• доступ до носія здійснюється послідовним чином: у кожен момент часу можна вважати або записати тільки елемент, наступний за поточним

• об'єм даних не дозволяє їм розміститися в ОЗУ.

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

Даний клас алгоритмів ділиться на два основні підкласи:

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

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

Існує велика кількість алгоритмів сортування, але всі вони базуються на трьох основних:

• сортування обміном;

• сортування вибором;

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

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

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

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

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

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

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

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

У загальній постановці завдання ставиться таким чином. Є послідовність однотипних записів, одне з полів яких вибране як ключовий (далі ми називатимемо його ключем сортування). Тип даних ключа повинен включати операції порівняння ("=", ">", "<", ">=" і "<="). Завданням сортування є перетворення початкової послідовності в послідовність, що містить ті ж записи, але в порядку зростання (або убування) значень ключа. Метод сортування називається стійким, якщо при його застосуванні не змінюється відносне положення записів з рівними значеннями ключа.

Розрізняють сортування масивів записів, цілком розташованих в основній пам'яті (внутрішнє сортування), і сортування файлів, що зберігаються в зовнішній пам'яті і не поміщаються повністю в основній пам'яті (зовнішнє сортування).

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

1. Сортування включенням Одним з найбільш простих і природних методів внутрішнього сортування є сортування з простими включеннями. Ідея алгоритму дуже проста:

1. Хай є масив ключів а, а, ..., а[n].

2. Для кожного елементу масиву, починаючи з другого, проводиться порівняння з елементами з меншим індексом (елемент а[i] послідовно порівнюється з елементами а, а[i-2] ...) і до тих пір, поки для чергового елементу а[j] виконується співвідношення а[j]> а, а[i] і а[j] міняються місцями.

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

Приклад сортування методом Шелла

Початковий стан масиву	8 23 5 65 44 33 1 6
Фаза 1 (сортируются элементы, расстояние между которыми четыре)	8 23 5 65 44 33 1 6 8 23 5 65 44 33 1 6 8 23 1 65 44 33 5 6 8 23 1 6 44 33 5 65
Фаза 2 (сортируются элементы, расстояние между которыми два)	1 23 8 6 44 33 5 65 1 23 8 6 44 33 5 65 1 23 8 6 5 33 44 65 1 23 5 6 8 33 44 65 1 6 5 23 8 33 44 65 1 6 5 23 8 33 44 65 1 6 5 23 8 33 44 65
Фаза 3 (сортируются элементы, расстояние между которыми один)	1 6 5 23 8 33 44 65 1 5 6 23 8 33 44 65 1 5 6 23 8 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 1 5 6 8 23 33 44 65

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

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

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

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

3. Далі сортуємо 2 групи по 8 елементів, починаючи з (а, а, а, а, а, а, а, а[14]).

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

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

Послідовність і так майже відсортована. Прискорення підтверджене численними дослідженнями і на практиці виявляється досить істотним.

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

2. Метод бульбашки ( метод також називається обмінним сортуванням з вибором)

Ідея цього методу відбита в його назві. Найлегші елементи масиву "спливають" вгору, "найважчі" - тонуть. Алгоритмічно це можна реалізувати таким чином. Ми проглядатимемо весь масив "від низу до верху" і міняти елементи, що стоять поряд, там випадку, якщо "нижній" елемент менший, ніж "верхній". Таким чином, ми виштовхнемо вгору "найлегший” елемент всього масиву. Тепер повторимо всю для тих, що залишилися неотсортироваными N-1 елементів (тобто для тих, які лежать "нижче" першого. Як видно, алгоритм достатньо простий, але, як іноді помічають, він є неперевершеним в своїй неефективності.

Алгоритм

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

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

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

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

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

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

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

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

Початковий стан масиву	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 33 6 1 8 5 23 65 44 33 6 1 8 5 23 65 44 33 6 1 8 5 23 44 65 33 6 1 8 5 23 44 33 65 6 1 8 5 23 44 33 6 65
Крок 3	1 8 5 23 44 6 33 65 1 8 5 23 6 44 33 65 1 8 5 6 23 44 33 65 1 8 5 6 23 44 33 65 1 5 8 6 23 44 33 65
Крок 4	1 5 6 8 23 44 33 65 1 5 6 8 23 44 33 65 1 5 6 8 23 44 33 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

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

3. Сортування вибором (методом знаходження минимального/максимального елементу)

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

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

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

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

Для знаходження найменшого елементу з n+1 розглянутих алгоритм здійснює n порівнянь.

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

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

Для перестановки елементів в масиві по убуванню їх значень необхідно при порівнянні елементів масиву замінити знак > на <.

8. Сортування масиву бульбашковим методом	9. Сортування масиву вибором найбільшого елементу

Алгоритм сортування вибором приведений у вигляді блок-схеми на мал. 9. Знайдемо в масиві найбільший елемент (блоки 3-7) і поміняємо його місцями з останнім елементом (блок 8). Повторюваний алгоритм пошуку максимального елементу, зменшивши кількість елементів, що проглядаються, на одиницю (блок 9), і поміняємо його місцями з передостаннім елементом (блоки 3-7). Описану вище операцію пошуку проводимо до повного впорядковування елементів в масиві. Оскільки в блоці 9 відбувається зміна змінній n, то на початку алгоритму її значення необхідно зберегти (блок 1).

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

Початковий стан масиву	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

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

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

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

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

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

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

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

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

1. Знайден елемент, менший x.

2. Досягнутий початок послідовності.

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

Тобто можна зробити вивід, що алгоритм сортування вставками полягає в тому, що

1. Спочатку упорядковуються два елементи масиву.

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

3. Четвертий елемент поміщають в список з вже впорядкованих трьох елементів.

4. Цей процес повторюється до тих пір, поки всі елементи не будуть впорядковані.

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

Мал. 10. Процес вставки елементу в масив

Складемо блок-схему алгоритму (мал. 11), враховуючи, що можливо описані вище дії доведеться виконати неодноразово.

Організовуємо цикл для проглядання всіх елементів масиву, починаючи з другого (блок 4). Збережемо значення поточного i-го елементу в допоміжній змінній X, оскільки воно може бути втрачене при зрушенні елементів (блок 5) і привласнимо змінною j значення індексу попереднього (i-1) -го елементу масиву (блок 6). Далі рухаємося по масиву вліво у пошуках елементу меншого, ніж поточний і поки він не знайдений зрушуємо елементи управо на одну позицію. Для цього організовуємо цикл (блок 7), який припинитися, як тільки буде знайдений елемент менше поточного. Якщо такого елементу в масиві не знайдеться і змінна j стане рівною нулю, то це означатиме, що досягнута ліва межа масиву, і поточний елемент необхідно встановити в першу позицію. Зсув елементів масиву управо на одну позицію виконується в блоці 8, а зміна лічильника j в блоці 9. Блок 10 виконує вставку поточного елементу у відповідну позицію.

Мал. 11. Сортування масиву вставкою