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

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

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

У цій статті постараємося це з'ясувати. Для забезпечення найкращих результатів всі представлені алгоритми будуть сортувати цілочисельний масив з 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 ст.12log2n). У гіршому випадку O (n ^ 2). Існує також середнє значення, це O (n ст.1log2n).

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

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

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

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

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

Висновки:

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