Constructive-synthesizing production of sorting programs adapted by genetic algorithm

V.I. Shynkarenko, O.V. Makarov

Abstract


In previous works, the mechanisms of constructive-synthesizing modeling for the adaptation of sorting algo rithms were presented. In this regard, the task of transforming the chromosomes of a genetic algorithm into the text of sorting programs for further application, evaluation and the possibility of evolutionary development arose. An approach to the transformation of the chromosome encoding a sorting algorithm into the text of a sorting program ready for use in real conditions is considered. A transformer constructor has been developed that im plements the transformation of a chromosome tree into a linear sequence of genes. Another transformer con structor is designed to transform a sequence of genes into the code of a sorting program. Examples of the sequence of traversing a chromosome tree, adding genes to a linear sequence and forming the text of the program are given. Experiments were conducted with input data of different structures and volumes. The results of the experiments confirmed that the proposed method can be used for the automatic generation of effective sorting algorithms. And the use of constructive-synthesizing modeling in conjunction with a genetic algorithm allows for the effective structural adaptation of algorithms.

Problems in programming 2026; 1: 40-50


Keywords


constructive-synthesizing modeling; sorting algorithm; time efficiency; genetic algorithm; software; information technology

References


Sedgewick R. Implementing quicksort programs // Communications of the ACM, 21(10), 847–857 (1978).

Knuth D. E. Sorting by Exchanging // The Art of Computer programming. – Vol. 3: Sorting and Searching. – 1st ed. – Addison-Wesley. pp. 110–111. – 1973.

Williams W. J. Algorithm 132 (heapsort) // Communications of the ACM, 7, 347–348. – 1964.

Song C. and Li H. Improvement of Counting Sorting Algorithm // In Journal of Computer and Communications, vol. 11, pp. 12–22, 2023.

Wassenberg J., Sanders P. Engineering a multi‑core radix sort // In Proc. Euro‑Par 2011, Part II, LNCS 6853, Bordeaux, France, 2011, pp. 160–169.

Faujdar N. and Saraswat S. The detailed experimental analysis of bucket sort // In Proceedings of the 7th International Conference on Cloud Computing, Data Science & Engineering – Confluence, IEEE, pp. 12–13, Jan. 2017.

Haeupler B. , Hladík R. , Iacono J., Rozhoň V., Tarjan R. E. and Tětek J. Fast and Simple Sorting Using Partial Information // In Proceedings of the 2025 Annual ACM‑SIAM Symposium on Discrete Algorithms (SODA), pp. 3953–3973, 2025.

Subramaniam M. , Tripathi T. and Chandraumakantham O. Cluster Sort: A Novel Hybrid Approach to Efficient In-Place Sorting Using Data Clustering // In IEEE Access, vol. 13, pp. 74359–74374, 2025.

Shinkarenko V. I. , Doroshenko A. Yu., Yatsenko O. A., Raznosilin V. V., Galanin K. K. Bicomponent sorting algorithms // Problems of Programming.– 2022. – No. 3–4. – pp. 32–41.

Shinkarenko V. I. , Makarov O. V. Study of the effectiveness of some deterministic preprocessing methods of data sorting // Problems of Programming. – 2023.– No. 4. pp. 3–14.

Shinkarenko V.I. , Makarov O.V. Structural Adaptation of Sorting Algorithms Based on Constructive Fragments // CEUR Workshop Proceedings. – Vol. 3806. – pp. 16–29.– 2024.

Shinkarenko V. I. , Makarov O. V. Constructive synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms // Problems of Programming. –2025. – No. 3. – pp. 39–52.

Beasley D. , Bull D. R. and Martin R. R. An Overview of Genetic Algorithms: Part 1, Fundamentals // in University Computing, vol. 15, pp. 58–69, 1993.

Shynkarenko V. I. , Ilman V. M. Constructive Synthesizing Structures and Their Grammatical Interpretations. I. Generalized Formal Constructive-Synthesizing Structure // Cybernetics and Systems Analysis. – Vol. 50, No. 5. – pp. 8–16.


Refbacks

  • There are currently no refbacks.