Effective Implementation of Sorting Algorithms Using the Concept of Q-determinant
https://doi.org/10.25205/1818-7900-2025-23-2-5-17
Abstract
The present paper is devoted to the possibility of efficient implementation for sorting algorithms using the Q-determinant concept. We have investigated four algorithms: shaker sort, Shell sort, quicksort and Batcher’s odd-even mergesort. To sort small arrays, we obtained representations in the form of Q-determinants for these algorithms. Then the structures of the obtained representations were analyzed and, as a result, for the general case we have described the representations of the sorting algorithms in the form of a Q-determinant. Also, for sorting algorithms there was considered the application of the method of designing effective programs using the concept of Q-determinant. This application has been tested on shared and distributed memory of parallel computing systems by developing eff ective programs for the Shell sort.
About the Authors
V. N. Aleeva
South Ural State University
Russian Federation
Russian Federation
Valentina N. Aleeva, Candidate of Science in Physics and Mathematics
Chelyabinsk
E. K. Kuznetsov
South Ural State University
Russian Federation
Russian Federation
Egor K. Kuznetsov, Master’s Degree Student
Chelyabinsk
References
1. Aleeva V. N. Analysis of Parallel Numerical Algorithms. Preprint no. 590. Novosibirsk, Computing Center of the Siberian Branch of the Academy of Sciences of the USSR, 1985, 23 p. (in Russ.)
2. Aleeva V., Aleev R. Investigation and Implementation of Parallelism Resources of Numerical Algorithms. ACM Transactions on Parallel Computing, 2023, vol. 10, no. 2, рр. 1‒64. DOI: 10.1145/3583755
3. Aleeva V. N., Zotova P. S., Skleznev D. S. Advancement of Research for the Parallelism Resource of Numerical Algorithms with the Help of Software Q-system. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering, 2021, vol. 10, no. 2, рр. 66‒81. (in Russ.) DOI: 10.14529/cmse210205
4. Aleeva V. N., Shatov M. B. Application of the Q-determinant Concept for Efficient Implementation of Numerical Algorithms by the Example of the Conjugate Gradient Method for Solving Systems of Linear Equations. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering, 2021, vol. 10, no. 3, рр. 56‒71. (in Russ.) 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, рр. 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, рр. 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. In: 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. In: Proceedings ‒ 2020 Global Smart Industry Conference, GloSIC 2020. IEEE, 2020. P. 113‒120. Article number 9267828. DOI: 10.1109/GloSIC50886.2020.9267828
10. Ershov Yu. L., Palyutin E. A. Mathematical Logic. Moscow, Mir publ., 1984, 303 p. (in Russ.)
11. Knuth D. The Art of Computer Programming. Vol. 3. Sorting and Searching, Second Edition. Moscow, LLC “I.D. Williams”, 2018, 832 p. (in Russ.)
Review
For citations:
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
Views:
88
Email this article 