Эффективная реализация алгоритмов сортировки с помощью концепции Q-детерминанта
https://doi.org/10.25205/1818-7900-2025-23-2-5-17
Аннотация
Статья содержит исследование возможности эффективной реализации алгоритмов сортировки с помощью концепции Q-детерминанта. Для проведения исследования используются алгоритмы шейкерной сортировки, сортировки Шелла, быстрой сортировки и четно-нечетной сортировки слиянием Бэтчера. Для этих алгоритмов получены представления в форме Q-детерминантов для сортировки массива, состоящего из небольшого количества элементов. Проведен анализ структуры полученных представлений. На основе результатов анализа описано представление алгоритма сортировки в форме Q-детерминанта для общего случая. Рассмотрено применение для алгоритмов сортировки метода проектирования эффективных программ, использующего концепцию Q-детерминанта. Применение метода апробировано с помощью разработки эффективных программ, реализующих алгоритм сортировки Шелла на общей и распределенной памяти параллельных вычислительных систем.
Об авторах
В. Н. Алеева
Южно-Уральский государственный университет
Россия
Россия
Алеева Валентина Николаевна, кандидат физико-математических наук
Челябинск
Е. К. Кузнецов
Южно-Уральский государственный университет
Россия
Россия
Кузнецов Егор Константинович, студент магистратуры
Челябинск
Список литературы
1. Алеева В. Н. Анализ параллельных численных алгоритмов. Препринт № 590. Новосибирск: ВЦ СО АН СССР, 1985. 23 с.
2. Aleeva V., Aleev R. Investigation and Implementation of Parallelism Resources of Numerical Algorithms // ACM Transactions on Parallel Computing. 2023. Vol. 10. No. 2. P. 1‒64. DOI: 10.1145/3583755
3. Алеева В. Н., Зотова П. С., Склезнев Д. С. Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы // Вестник ЮУрГУ . Серия: Вычислительная математика и информатика. 2021. Т. 10, № 2. С. 66‒81. DOI: 10.14529/cmse210205
4. Алеева В. Н., Шатов М. Б. Применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 3. С. 56‒71. DOI: 10.14529/cmse210304
5. Aleeva V. Designing a Parallel Programs on the Base of the Conception of Q-Determinant // Supercomputing. RuSCDays 2018. Communications in Computer and Information Science. 2019. Vol. 965. P. 565‒577. DOI: 10.1007/978-3-030-05807-4_48
6. Aleeva V. N., Sharabura I. S., Suleymanov D. E. Software System for Maximal Parallelization of Algorithms on the Base of the Conception of Q-determinant // Parallel Computing Technologies (PaCT 2015). Lecture Notes in Computer Science. 2015. Vol. 9251. P. 3‒9. DOI: 10.1007/978-3-319-21909-7_1
7. Aleeva V. N., Aleev R. Zh. High-Performance Computing Using Application of Q-determinant of Numerical Algorithms // Proceedings ‒ 2018 Global Smart Industry Conference, GloSIC 2018. IEEE. 2018. 8 p. Article number 8570160. DOI: 10.1109/GloSIC.2018.8570160
8. Aleeva V., Bogatyreva E., Skleznev A. et al. Software Q-system for the Research of the Resource of Numerical Algorithms Parallelism // Supercomputing. RuSCDays 2019. Communications in Computer and Information Science. 2019. Vol. 1129. P. 641‒652. DOI: 10.1007/978-3-030-36592-9_52
9. Aleeva V. N. Improving Parallel Computing Effi ciency // Proceedings ‒ 2020 Global Smart Industry Conference, GloSIC 2020. IEEE. 2020. P. 113‒120. Article number 9267828. DOI: 10.1109/GloSIC50886.2020.9267828
10. Ершов Ю . Л., Палютин Е. А. Математическая логика. М.: Наука, 1987. 336 с. 11. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск, 2-е изд. М.: Вильямс, 2018. 832 с.
Рецензия
Для цитирования:
Алеева В.Н., Кузнецов Е.К. Эффективная реализация алгоритмов сортировки с помощью концепции Q-детерминанта. Вестник НГУ. Серия: Информационные технологии. 2025;23(2):5-17. https://doi.org/10.25205/1818-7900-2025-23-2-5-17
For citation:
Aleeva V.N., Kuznetsov E.K. Effective Implementation of Sorting Algorithms Using the Concept of Q-determinant. Vestnik NSU. Series: Information Technologies. 2025;23(2):5-17. (In Russ.) https://doi.org/10.25205/1818-7900-2025-23-2-5-17
Просмотров:
23
Послать статью по эл. почте 