Сортування «Злиття»: опис та реалізація різними мовами

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

Далі належить познайомитися з сортуванням масиву злиттям. Це один із найпростіших та ефективніших алгоритмів. Також до уваги будуть представлені інші підходи до впорядкування елементів масиву. Ця інформація допоможе зрозуміти різницю між алгоритмами та пояснить особливості підходу «злиття».

Коротка характеристика

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

Тут, якщо два елементи масиву (int) мають однакові значення, вони займають те ж відносне положення у відсортованій послідовності, що і у вхідних даних. У відсортованій множині зберігається відносний порядок складових з однаковими значеннями. "Злиття" - це сортування елементів масиву (int) порівнянням. Алгоритм є наочним прикладом принципу «розділяй і володарюй».

Алгоритм роботи

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

Виконується аналізований підхід до упорядкування елементів масиву (int) за кілька кроків:

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

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

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

Вище можна побачити наочний приклад упорядкування масиву з цілих (int) елементів. Усього в заданому ланцюжку 7 складових.

Переваги та недоліки

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

До переваг відповідного підходу можна віднести:

1. Стабільність. Упорядкування елементів масиву (int) з допомогою даного алгоритму – це підтримка відносного порядку рівних компонентів у вхідному масиві.
2. Продуктивність при найгіршому розкладі. Тимчасова складність алгоритму сортування злиттям дорівнює O(N logN). Це означає, що відповідний підхід працює добре навіть на великих наборах вихідних даних.
3. Простоту реалізації. Метод «поділяй і володарюй» є досить простим і зрозумілим. Освоїти його зможе навіть розробник-початківець.

Сортування злиттям також має деякі недоліки. До них відносять такі моменти:

1. Просторова складність. Реалізація алгоритму вимагає додаткової пам'яті. Вона виділяється для зберігання об'єднаних підмасивів у процесі роботи методу.
2. "Не на місці". Розглянута концепція упорядкування елементів масиву (int) перестав бути алгоритмом сортування «на місці». Це означає, що для зберігання відсортованих даних необхідно виділяти додаткову пам'ять.Для деяких програм відповідний момент може стати справжньою проблемою.

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

Області застосування

Розглянутий алгоритм злиття масивів (int) рекомендується використовувати певних завдань. До них відносять:

• упорядкування елементів у великих інформаційних наборах;
• зовнішнє сортування – коли вихідний набір даних занадто великий розміщувати у пам'яті;
• підрахунок інверсій;
• знаходження медіани заданого масиву.

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

Приклад на Java

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

Тут потрібно написати функцію merge sort. Вона прийматиме вхідний масив і його довжину як параметри. Ця функція є рекурсивною, тому потрібна база та рекурсивні умови.

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

Для рекурсивного випадку необхідно отримати середній індекс та створити два тимчасові масиви (підмасиву): l[] та r[]. Тепер рекурсивно здійснюється виклик функції merge sort для обох підмасивів:

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

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

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

А ось так виглядає модульний тест для алгоритму, що вийшов:

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

Приклади для C та Python

Реалізація merge sort у C буде мати такий вигляд:

Для Python реалізація виявиться такою:

Тепер можна вивчити інші підходи до упорядкування елементів заданого масиву.

Пухирцевий похід

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

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

Перемішування

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

«гребінець»

Метод «гребінець» – це модифікація бульбашкового алгоритму під час роботи з безліччю int. Її ідея полягає в тому, щоб «відсіяти» компоненти з невеликими значеннями та розмістити їх у самому кінці ланцюжка. Цей прийом значно прискорює роботу методу.

При «розчісуванні» спочатку необхідно взяти досить велику відстань між двома порівнюваними значеннями int, а потім поступово звужувати його аж до мінімального. Початковий розрив вибирається не випадковим чином, а з допомогою чинника зменшення. Його оптимальне значення дорівнює 1247. Це означає, що відстань між двома int у заданому ланцюжку дорівнюватиме розміру масиву, поділеного на фактор зменшення. На кожному наступному етапі відстань знову ділиться на 1,247. Робити так потрібно до закінчення роботи алгоритму.

Вставка

Сортування двох масивів досить великого обсягу може здійснюватися з допомогою «злиття». Для ланцюжків int невеликих розмірів варто скористатися простим алгоритмом. Він називається "вставка".

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

Вибір

Ще один простий варіант упорядкування ланцюжків int. При алгоритмі «вибір» спочатку необхідно розглянути підмножину заданого масиву та визначити у ньому максимум чи мінімум. Далі – обране значення поміняти місцями зі значенням першої невідсортованої множини int. Цей крок виконується доти, доки в ланцюжку не закінчаться невідсортовані підмасиви.

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

Швидке сортування – це підхід, який виконується у три етапи:

1. Спочатку із заданої множини int необхідно вибрати один компонент - опорний.
2. Інші складові множини int перерозподіляються так, щоб елементи менше опорного розташовувалися до нього, а великі або рівні - після.
3. Рекурсивно застосовуються перші два кроки в заданих підмасивах праворуч та ліворуч від опорного значення.

Такий підхід, як і merge sort, є ефективним. Швидке сортування з'явилося 1960 року. Вона використовувалася для машинного перекладу: тоді словники розміщувалися на спеціальних магнітних стрічках, а впорядкування слів тексту, що обробляється, давало можливість отримувати переклади всього за один прогін стрічки.

Бажаєте освоїти сучасну IT-спеціальність? Величезний вибір курсів по затребуваним IT-напрямкам є в Otus!

Порівняння алгоритмів сортування

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

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

У цій статті намагатимемося це з'ясувати. Для забезпечення найкращих результатів усі представлені алгоритми будуть сортувати цілий масив з 200 елементів. Комп'ютер, на якому буде проводитися тестування, має наступні характеристики: процесор AMD A6-3400M 4x1.4 GHz, оперативна пам'ять 8 GB, операційна система Windows 10 x64 build 10586.36.

Для проведення дослідження було обрано такі алгоритми сортування:

Selection sort (сортування вибором) – суть алгоритму полягає у проході по масиву від початку до кінця у пошуку мінімального елемента масиву та переміщенні його на початок. Складність такого алгоритму O(n2).

Bubble sort (сортування бульбашкою) – даний алгоритм змінює місцями два сусідні елементи, якщо перший елемент масиву більший за другий. Так відбувається доти, доки алгоритм не обміняє місцями всі невідсортовані елементи. Складність цього алгоритму сортування дорівнює O(n^2).

Insertion sort (сортування вставками) – алгоритм сортує масив у міру проходження його елементами. На кожній ітерації береться елемент і порівнюється з кожним елементом у вже відсортованій частині масиву, таким чином знаходячи своє місце, після чого елемент вставляється на свою позицію. Так відбувається доти, доки алгоритм не пройде по всьому масиву. На виході отримаємо відсортований масив. Складність цього алгоритму дорівнює O(n^2).

Quick sort (швидке сортування) – суть алгоритму полягає у поділі масиву на два підмасиву, середньою лінією вважається елемент, який знаходиться в самому центрі масиву. У ході роботи алгоритму елементи, менші ніж середній, будуть переміщені вліво, а більші в право. Така ж дія відбуватиметься рекурсивно і з підмасиву, вони будуть поділятися на ще два підмасиви доти, поки не буде чого обробити (залишиться один елемент). На виході отримаємо відсортований масив. Складність алгоритму залежить від вхідних даних і в кращому випадку дорівнюватиме O(n×2log2n). У найгіршому випадку O(n^2). Існує також середнє значення, це O(n×log2n).

Comb sort (сортування гребінцем) - Ідея роботи алгоритму вкрай схожа на сортування обміном, але головною відмінністю є те, що порівнюються не два сусідні елементи, а елементи на проміжку, наприклад, п'ять елементів. Це забезпечує від позбавлення дрібних значень наприкінці, що сприяє прискоренню сортування великих масивах. Перша ітерація відбувається з кроком, розрахованим за формулою (розмір масиву)/(фактор зменшення), де фактор зменшення дорівнює приблизно 1,247330950103979, або округлено до 1,3. Друга та наступні ітерації будуть проходити з кроком (поточний крок)/(фактор зменшення) і відбуватимуться доти, доки крок не дорівнюватиме одиниці. Практично у разі складність алгоритму дорівнює O(n×log2n).

Для проведення тестування буде здійснено по 5 запусків кожного алгоритму та вибрано найкращий час. Найкращий час і пам'ять, що використовується при цьому, будуть занесені в таблицю. Також буде проведено тестування швидкості сортування масиву розміром 10, 50, 200 та 1000 елементів, щоб визначити для яких завдань призначений конкретний алгоритм.

Повністю невідсортований масив:

Частково відсортований масив (половина елементів упорядкована):

Результати, надані у графіках:

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

• C++
• алгоритми
• сортування
• сортування гребінцем
• сортування бульбашкою
• швидке сортування
• сортування масиву
• алгоритм сортування
• сортування вставками