КОНСТРУЮВАННЯ АЛГОРИТМІВ СОРТУВАННЯ
DOI:
https://doi.org/10.34185/1991-7848.itmm.2025.01.055Ключові слова:
конструктивно-продукційне моделювання, програмне забезпечення, інформаційні технології, алгоритм, формальні граматики, генетичний алгоритм.Анотація
З розвитком цифрових технологій та збільшенням обсягів оброблюваних даних ефективність алгоритмів сортування набуває критичного значення. У роботі розглянуто еволюцію сортувальних алгоритмів від класичних до гібридних методів, зокрема Timsort та Introsort, які демонструють покращені часові характеристики та стабільність у порівнянні з традиційними підходами. Окрема увага приділена методам передобробки даних та їх впливу на продуктивність. Запропоновано підхід конструктивно-продукційного моделювання для створення адаптивних алгоритмів сортування, що дозволяє комбінувати існуючі методи та формувати нові ефективні алгоритми. Використання генетичного алгоритму у процесі конструювання дозволяє автоматизувати вибір оптимальних стратегій сортування відповідно до характеристик вхідних даних. Отримані результати підтверджують перспективність застосування конструктивно-продукційного підходу для побудови адаптивних алгоритмів сортування, що забезпечують високу продуктивність у різних умовах.
Посилання
Peters T. Timsort description, accessed june 2015. http://svn.python.org/projects/python/trunk/Objects/listsort.txt.
David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley. – 1989. p. 412.
Shinkarenko V. I., Makarov O. V. Study of the Efficiency of Some Certain Deterministic Preprocessing Methods for Sorting Algorithms. Problems of Programming – 2023. No. 4. pp. 3–14. doi: 10.15407/pp2023.04.003
Shinkarenko V. I., Doroshenko A. Yu., Yatsenko O. A., Raznosilin V. V., Galanin K. K., Data Stochastic Preprocessing for Sorting Algorithms, CEUR in: Proceedings of the 13th International Scientific and Practical Programming Conference UkrPROG 2022, vol. 3501, 29- 38.
Marceau, Robert R. An Analysis of the Worst-Case Performance of Quicksort. Rivier Academic Journal – 2011. № 7.1.
Havrylenko S. Yu. Formal Languages, Grammars, and Automata. Kharkiv: NTU «KhPI» – 2021. p. 133.
Shinkarenko V. I., Makarov O. V. Structural Adaptation of Sorting Algorithms Based on Constructive Fragments. CEUR-WS. – 2024. № 3806. p. 16-29.
