Порівняльний аналіз часової та просторової складності алгоритмів сортування в сучасних програмних середовищах

Артем Олександрович Іванов; Олександр Миколайович Кривонос

doi:10.26642/ten-2026-1(97)-217-225

Автор(и)

Артем Олександрович Іванов Житомирський державний університет імені Івана Франка, Україна https://orcid.org/0009-0006-2704-9906
Олександр Миколайович Кривонос Житомирський державний університет імені Івана Франка, Україна https://orcid.org/0000-0002-4211-6541

DOI:

https://doi.org/10.26642/ten-2026-1(97)-217-225

Ключові слова:

алгоритми сортування, часова складність, просторова складність, асимптотичний аналіз, Big Data, адаптивність алгоритмів, Python, метод Акра-Баззі, Big O нотація, порівняльне тестування

Анотація

Стаття присвячена комплексному дослідженню та порівняльному аналізу найбільш розповсюджених алгоритмів сортування, таких як бульбашкове, вставками, вибором, злиттям, швидке, купами та коміркове сортування. Актуальність роботи зумовлена стрімким розвитком технологій Big Data та Інтернету речей (IoT), що вимагає високої ефективності обробки даних в умовах як необмежених обчислювальних потужностей, так і екстремально обмежених ресурсів пам’яті. Автори детально розглядають теоретичні аспекти кожного алгоритму, проводячи математичне моделювання їхньої часової та просторової складності за допомогою асимптотичного аналізу та методу Акра-Баззі для рекурентних структур.

Методологія дослідження поєднує теоретичний аналіз асимптотик із емпіричним тестуванням продуктивності в середовищі Python 3.14 на сучасній архітектурі процесору Ryzen 7 7445HS. У роботі досліджуються не лише показники швидкодії на випадкових масивах, а й властивість адаптивності алгоритмів до вже впорядкованих або частково впорядкованих даних. Результати експериментів наочно демонструють, як вибір опорного елемента у швидкому сортуванні або специфіка менеджменту стеку викликів впливають на реальний час виконання та обсяг використаної пам’яті.

На основі отриманих даних сформовано практичні рекомендації щодо застосування конкретних методів сортування залежно від апаратних обмежень та характеру вхідних даних. Встановлено, що коміркове сортування є найбільш ефективним для великих масивів за наявності достатнього обсягу оперативної пам’яті, тоді як сортування купами (Heap Sort) виявляється оптимальним за просторовою складністю серед алгоритмів класу O(n \log n). Для специфічних умов впорядкованих даних найкращі результати за швидкістю показало сортування вставками. Стаття має наукову та практичну цінність для розробників програмного забезпечення, які прагнуть оптимізувати процеси індексації та аналізу великих обсягів інформації.

Посилання

GeeksforGeeks (2025), Akra-Bazzi method for finding the time complexities, [Online], available at: https://www.geeksforgeeks.org/dsa/akra-bazzi-method-for-finding-the-time-complexities/

Ashok, K.K. (2014), A Survey, Discussion and Comparison of Sorting Algorithms, Umeå University, Department of Computing Science, [Online], available at: https://www.diva-portal.org/smash/get/diva2:739880/FULLTEXT01.pdf

GeeksforGeeks (2025), Bucket Sort, [Online], available at: https://www.geeksforgeeks.org/dsa/bucket-sort-2/

Goel, K., Dwivedi, P. and Sharma, O. (2023), «Performance Analysis of Various Sorting Algorithms: Comparison and Optimization», 2023 11th International Conference on Intelligent Systems and Embedded Design (ISED), pp. 1–5, doi: 10.1109/ISED59382.2023.10444609.

GeeksforGeeks (2026), Heap Sort, [Online], available at: https://www.geeksforgeeks.org/dsa/heap-sort/

Karuna, S. (2018), An Introduction to Bucket Sort, [Online], available at: https://medium.com/karuna-sehgal/an-introduction-to-bucket-sort-62aa5325d124

Mohammed, A., Zhanar, M., Alaa, F.A. et al. (2024), «Comparative Analysis of Sorting Algorithms: A Review», 11th International Conference on Soft Computing & Machine Intelligence, pp. 1–8.

Pizarro-Vasquez, G.O. et al. (2021), «Sorting Algorithms and Their Execution Times an Empirical Evaluation», in Botto-Tobar, M. et al. (ed.), Advances in Emerging Trends and Technologies, pp. 329–340, doi: 10.1007/978-3-030-63665-4_27.

Sakpal, N. et al. (2024), Comparative Analysis of Sorting and Searching Algorithms, SSRN, [Online], available at: https://ssrn.com/abstract=4815467

Santos, A.B.G. et al. (2021), «Asymptotic Analysis of the Running Time Performed by Various Sorting Algorithms», 2021 International Conference on Intelligent Technologies (CONIT), IEEE, pp. 1–6, doi: 10.1109/CONIT51480.2021.9498490.