Порівняння швидкодії алгоритмів сортування у різних мовах програмування

Сфери застосування базових алгоритмів сортування

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

Результати дослідження

У практичні частині дослідження ми порівнювали фактичний час роботи кожного алгоритму для наборів псевдовипадкових чисел від 100 до 100 000 елементів для кожної з вибраних мов програмування: C++, Java, JavaScript та С#. Числові 64-бітні цілі псевдовипадкові значення були згенеровані вбудованими засобами кожної конкретної мови. Розміри масивів для всіх мов однакові: {100, 300, 500, 1000, 1500, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 50000, 60000, 70000, 80000, 90000, 100000}. Апаратно-програмна складова дослідження: ноутбук на базі процесора Ryzen 5 5600H; Java - JDK 20; C++ - LLVM GCC Compiler 16.0; C# - .NET 7.0; JS - Nodejs 19.8.1. Часом вважали середнє арифметичне значення п'яти вимірювань часу роботи алгоритму, оскільки цей підхід демонструє свою ефективність у багатьох дослідженнях [3] - [11]. Одиниці виміру - мілісекунди (у випадку, якщо вбудована функція повертала результат в інших одиницях, він підлягав конвертації).

Функції та типи результатів функцій, використаних для визначення часу в різних мовах:

- JS - process.hrtime.bigint() - повертає системний час у високій роздільній здатності у наносекундах у BigInt;

- Java - Sysytem.TimeNano() - повертає час у наносекундах у long;

- C++ - auto startTime = std::chrono::high_resolution_clock::now() - метод

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

- C# - методи класу StopWatch, який відноситься до System.Diagnostics, повертає тип TimeSpan і в подальшому конвертується у рядок.

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

На рис. 1,а та 1,б наведено порівняння швидкодії алгоритмів сортування при реалізації мовами C++ та Java для кількості елементів в інтервалі від 100 та 100 000 елементів. Тут і далі з візуалізації виключені три найповільніші алгоритми сортування бульбашкою, вибором та вставкою, оскільки вони мають доволі великі показники в усіх мовах і на їх фоні важко спостерігати й аналізувати тенденції поведінки інших шести алгоритмів. Про порядок відповідних значень можна судити по даних, наведених у табл. 2. Із рис. 1,а та 1,б видно, що найшвидшими для великих масивів даних є (у порядку спадання ефективності) сортування підрахунком, за розрядами, швидке і купою. Ретельний аналіз виявив певні відмінності поведінки часової складності алгоритмів сортування злиттям і Шелла. Так, при реалізації мовою Java алгоритм сортування злиттям виявився швидшим за сортування Шелла. При реалізації засобами С++ алгоритм сортування Шелла навпаки працює повільніше за алгоритм сортування злиттям.

Таблиця 2

Швидкодія алгоритмів сортування при реалізації засобами мови Java

Рисунок 1 - Порівняння швидкодії алгоритмів сортування мовами C+ + та Java

Рисунок 2 - Порівняння швидкодії алгоритмів сортування мовою C#

На рис. 2 наведено результати роботи шести алгоритмів сортування мовою C#. Встановлено, що найшвидшими є сортування підрахунком та за розрядами. Далі за спаданням швидкодії йдуть сортування Шелла, злиттям, купою і швидке.

На рис. 3 наведено результати роботи шести алгоритмів сортування мовою JavaScript. Для малих масивів найкращі результати показали алгоритми сортування купою і Шелла. Для наборів даних понад 60 тис. елементів найкращим виявився алгоритм сортування підрахунком, випереджаючи сортування купою і Шелла, які мають майже однакову ефективність. Швидке сортування, злиттям та розрядами посідають відповідно з четвертого по шосте місця.

Рисунок 3 - Швидкодія алгоритмів сортування мовою JavaScript

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

Висновки та перспективи подальших досліджень

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

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

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

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

Список використаних джерел

1 Big-O Complexity Chart. https://www.bigocheatsheet.com/

2 Корнійчук, М.М., Трофименко, О.Г. (2023) Оцінка часової складності деяких алгоритмів сортування у популярних мовах програмування. Інформаційне суспільство: проблеми та перспективи : матер. VIII всеукр. наук.-практ. конф., 72-74, https://doi.org/10.32837/11300.25263.

3 Marcellino, M., Pratama, D. W., Suntiarko, S. S., Margi, K. (2021). Comparative of Advanced Sorting Algorithms (Quick Sort, Heap Sort, Merge Sort, Intro Sort, Radix Sort) Based on Time and Memory Usage. 1st International Conference on Computer Science and Artificial Intelligence (ICCSAI), 1, 154-160. https://doi.org/10.1109/ICCSAI53272.2021.9609715.

4 Ali, I., Lashari, H., Keerio, I., Maitlo, A., Chhajro, M., Malook, M. (2018). Performance Comparison between Merge and Quick Sort Algorithms in Data Structure. International Journal of Advanced Computer Science and Applications, 9, 192-195. https://doi.org/10.14569/IJACSA.2018.091127.

5 Rabiu, A., Garba, E., Baha, B., Mukhtar, M. (2021). Comparative Analysis between Selection Sort and

Merge Sort Algorithms. Nigerian Journal of Basic and Applied Sciences, 29, 43-48.

https://doi.org/10.4314/njbas.v29iL5.

6 Rabiu, A., Garba, E., Baha, B., Malgwi, Y., Dauda, M. (2022). Performance Comparison of three Sorting Algorithms Using Shared Data and Concurrency Mechanisms in Java. Arid-zone Journal of Basic & Applied Research (AJBAR), 1, 55-64. https://doi.org/10.55639/607fox.

7 Hermehar, B., Amandeep, K. (2022). Comparative Study of Different Sorting Algorithms used in Data

Structures. International Journal of Research Culture Society, 6, 114-119.

https://doi.org/10.2017/IJRCS/202203021.

8 Manan, C., Anurag, D. (2022). Establishing Pertinence between Sorting Algorithms Prevailing in nlog(n)

time. Journal of Robotics and Automation Research, 3(2), 220-226.

https://doi.org/10.33140/JRAR.03.02.09.

9 Durrani, O. K. (2023). Asymptotic performances of popular programming languages for popular sorting

algorithms. Semiconductor Optoelectronics, 42, 149-169.

https://www.researchgate.net/publication/369196272_asymptotic_performances_of_popular_programmin g_languages_for_popular_sorting_algorithms.

10 Butt, Sh., Aqib, S., Nawaz, H. (2021). Analysis of Merge Sort and Bubble Sort Python, PHP, JavaScript, and C language. International Journal of Advanced Trends in Computer Science and Engineering, 10, 680686. https://doi.org/10.30534/ijatcse/202m 11022021.

11 Fagbote, O.O. (2022). Performance evaluation of sorting techniques. Global Scientific Journal, 10(1), 112. https://www.globalscientificjournal.com/researchpaper/

performance_evaluation_of_sorting_techniques.pdf.

12 Khan, M., Shaheen, S., Qureshi, F. (2014). Comparative Analysis of five Sorting Algorithms on the basis

of Best Case, Average Case, and Worst Case. International Journal of Information Technology and Electrical Engineering, 3(1), 1-10.

https://www.researchgate.net/publication/310953713_Comparative_Analysis_of_five_Sorting_Algorithm s_on_the_basis_of_Best_Case_Average_Case_and_Worst_Case.

13 Durrani, O. K. (2022). Performance Measurement of Popular Sorting Algorithm Implemented using Java & C. International Conference on Electrical, Computer, Communications and Mechatronics Engineering (ICECCME), https://doi.org/10.1109/ICECCME55909.2022.9988424.

14 Fagbola, M., Surendra, T. (2019). Investigating the Effect of Implementation Languages and Large Problem

Sizes on the Tractability and Efficiency of Sorting Algorithms. International Journal of Engineering Research and Technology, 12, 196-203.

https://www.researchgate.net/publication/331408485_Investigating_the_Effect_of_Implementation_Lang uages_and_Large_Problem_Sizes_on_the_Tractability_and_Efficiency_of_Sorting_Algorithms.

15 PYPL PopularitY of Programming Language. https://pypl.github.io/PYPL.html.

16 TIOBE Index for June 2023. URL: https://www.tiobe.com/tiobe-index/

17 The RedMonk Programming Language Rankings: January 2023.

https://redmonk.com/sogrady/2023/05/16/language-rankings-1-23/

18 IEEE Spectrum. Top Programming Languages 2022. https://spectrum.ieee.org/top-programming- languages-2022

19 DOU. Рейтинг мов програмування 2023. https://dou.ua/lenta/articles/language-rating-2023/

20 numpy.sort. https://numpy.org/doc/stable/reference/generated/numpy.sort.html.

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