Constructive-synthesizing production of sorting programs adapted by genetic algorithm
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...
Збережено в:
| Дата: | 2026 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2026
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/890 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| _version_ | 1863311599553478656 |
|---|---|
| author | Shynkarenko, V.I. Makarov, O.V. |
| author_facet | Shynkarenko, V.I. Makarov, O.V. |
| author_sort | Shynkarenko, V.I. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2026-04-23T22:26:13Z |
| description | 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 |
| first_indexed | 2026-04-24T01:00:15Z |
| format | Article |
| fulltext |
Програмна інженерія – прикладні методи
40
© В.І. Шинкаренко, О.В. Макаров, 2026
ISSN 1727-4907. Проблеми програмування. 2026. №1
УДК 004.4 https://doi.org/10.15407/pp2026.01.040
В.І. Шинкаренко, О.В. Макаров
КОНСТРУКТИВНО-ПРОДУКЦІЙНЕ ФОРМУВАННЯ
ПРОГРАМ СОРТУВАННЯ, АДАПТОВАНИХ ГЕНЕТИЧНИМ
АЛГОРИТМОМ
У попередніх роботах представлені механізми конструктивно-продукційного моделювання для адаптації
алгоритмів сортування. У зв’язку з цим виникли задачі перетворення хромосом генетичного алгоритму
на текст програм сортування для подальшого застосування, оцінки можливостей еволюційного розвитку.
Розглядається підхід до перетворення хромосом, що кодують алгоритми сортування на тексти програм
готових до застосування у реальних умовах. Розроблено конструктор-трансформер, який реалізує пере-
творення хромосоми-дерева на лінійну послідовність генів. Інший конструктор-трансформер призначе-
ний для перетворення послідовності генів на код програми сортування. Наведено приклади
послідовності обходу дерева-хромосоми, додавання генів до лінійної послідовності і формування тексту
програми. Проведено експерименти із вхідними даними різної структури і обсягів. Результати експери-
ментів підтвердили, що запропонована методика може бути використана для автоматичної генерації ефе-
ктивних алгоритмів сортування. А застосування конструктивно-продукційного моделювання у
сукупності із генетичним алгоритмом дозволяє ефективно виконувати структурну адаптацію алгоритмів.
Ключові слова: конструктивно-продукційне моделювання, алгоритми сортування, часова ефективність, ге-
нетичний алгоритм, програмне забезпечення, інформаційні технології.
V.I. Shynkarenko, O.V. Makarov
CONSTRUCTIVE-SYNTHESIZING PRODUCTION OF SORTING
PROGRAMS ADAPTED BY GENETIC ALGORITHM
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.
Key words: constructive-synthesizing modeling, sorting algorithm, time efficiency, genetic algorithm, software,
information technology.
Вступ
Сортування – один із фундаменталь-
них будівельних блоків алгоритмічної ін-
женерії. Класичні порівняльні методи, такі
як quicksort [1], mergesort [2] і heapsort [3]
формують «базову лінійку» загального
призначення, демонструючи очікувану об-
числювальну складність 𝑂𝑂(𝑛𝑛 log 𝑛𝑛) у серед-
ньому чи в гіршому випадку. Непорів-
няльні підходи – counting sort [4], radix sort
[5], bucket sort [6] – досягають лінійних меж
𝑂𝑂(𝑛𝑛) за умови обмеженого діапазону або
специфічного розподілу ключів у вхідних
даних. Не дивлячись на класичні алго-
римти, які розробляються давно, зараз про-
довжується різностороння діяльність з
їхнього вдосконалення.
Одним із яскравих прикладів сучас-
ного прогресу є робота “Fast and Simple
Sorting Using Partial Information” [7], де ро-
зглядається проблема сортування з частко-
https://pp.isofts.kiev.ua
CC BY 4.0
Програмна інженерія – прикладні методи
41
вою інформацією, коли деякі попарні порі-
вняння вже відомі. Деяка кількість попере-
дніх порівнянь доступні, і завдання полягає
в тому, щоб використати мінімальну кіль-
кість нових порівнянь для повного відсор-
тування даних.
Паралельно тривають дослідження
алгоритмів, які використовують локаль-
ність даних та їхню кластерну структуру
для прискорення сортування. Новітній
представник цього напряму – Cluster Sort
[8], запропонований як гібридний in-place
підхід: елементи групуються (кластеризу-
ються) з урахуванням просторової локаль-
ності, після чого в межах кластерів
застосовуються ефективні процедури впо-
рядкування.
Наразі запропоновано декілька видів
детермінованих передобробок даних, приз-
начених для сортування [9, 10]. Проведені
експерименти, які показали, що викори-
стання передобробок може підвищити ча-
сову ефективність алгоритмів сортування.
Тому доцільно використати алгоритми пе-
редобробки у процесі формування алго-
ритмів сортування. Це розширює
можливості для конструювання, значно
збільшує варіативність сформованих алго-
ритмів, однак привносить додаткові пра-
вила та обмеження. Через те, що алгоритми
передобробки мають схожий принцип дії,
недоцільне послідовне використання кіль-
кох алгоритмів передобробки, що унемож-
ливлює використання двох алгоритмів
передобробки одночасно.
У статті [11] була запропонована
конструктивна модель хромосоми, в якій
алгоритм сортування кодується як набір
елементарних складових (production‑based
fragments), що можуть комбінуватися, роз-
ширюватися та еволюціонувати. Подання
алгоритму у вигляді конструктора, де час-
тини алгоритмів сортування виступають як
будівельні блоки, дозволяє:
поєднувати фрагменти різних класи-
чних алгоритмів сортування;
автоматично створювати гібридні
алгоритми;
адаптувати структуру алгоритму під
конкретні властивості даних і умови
застосування.
У продовження попередньої статті
[12], де було сформовано підхід до констру-
ктивно‑продукційного моделювання хро-
мосом, застосовано розроблену методику
для дослідження та структурної адаптації
алгоритмів сортування. За допомогою
конструктора-трансформера, виконується
декодування хромосоми у послідовність ге-
нів. Конструктор формування тексту про-
грам перетворює отриману послідовність
на код програми обраною мовою програму-
вання.
Виконані експерименти у яких конс-
труйовані алгоритми сортування застосову-
ються у різних обсягах і даних. За
допомогою генетичного алгоритму [13] ви-
конується адаптація структури сформова-
них алгоритмів до специфічних харак-
теристик вхідних даних, що дозволяє отри-
мувати алгоритми з кращими часовими по-
казниками у заданих умовах використання.
Конструктор-трансформер
Конструктор-трансформер реалізує
перетворення дерева-хромосоми із закодо-
ваними складовими алгоритму сортування
на масив (послідовність) генів.
Визначимо спеціалізацію констру-
тора CCD на основі узагальненого кострук-
тора C [14]:
𝐶𝐶 = ⟨Μ, Σ, Λ⟩ ⟼𝑠𝑠 𝐶𝐶𝐶𝐶𝐶𝐶
= ⟨Μ𝐶𝐶𝐶𝐶, Σ𝐶𝐶𝐶𝐶, Λ𝐶𝐶𝐶𝐶⟩, (1)
де Μ – неоднорідний розширюваний носій
структури, Σ – сигнатура, що складається з
множин операцій зв'язування, підстановки і
виводу, операцій над атрибутами і відно-
шення підстановки, Λ – інформаційне за-
безпечення конструювання, яке включає
онтологію, цілі, правила і обмеження кон-
струювання; Μ𝐶𝐶𝐶𝐶 – носій, що включає тер-
мінальний (𝑇𝑇𝐶𝐶𝐶𝐶) і нетермінальний (𝑁𝑁𝐶𝐶𝐶𝐶)
алфавіт, а також множину правил продукції
Ψ з правилами 𝜓𝜓𝑖𝑖 = 〈𝑠𝑠i , 𝑔𝑔i 〉 ∈ Ψ, де i – но-
мер правила, 𝑠𝑠i – послідовність відношень
підстановки та 𝑔𝑔i – операцій над атрибу-
тами. Σ𝐶𝐶𝐶𝐶 – операції та відносини на елеме-
нтах Μ𝐶𝐶𝐶𝐶. Інформаційне забезпечення
конструювання (ІЗК) Λ𝐶𝐶𝐶𝐶 ⊃ Λ.
Конструктор C𝐶𝐶𝐶𝐶 містить правила пі-
дстановки 𝜓𝜓𝑖𝑖 = 〈 〈𝑠𝑠𝑖𝑖,1, 𝑠𝑠𝑖𝑖,2〉, 〈𝑔𝑔i,1 , 𝑔𝑔i,2 〉〉, де
Програмна інженерія – прикладні методи
42
відношення 𝑠𝑠𝑖𝑖,1 реалізує розбір хромосоми
з використанням стеку для збереження про-
міжних результатів. Відношення 𝑠𝑠𝑖𝑖,2 приз-
начене для формування списку генів.
Операції виконуються у наступній
послідовності: спочатку виконуються опе-
рації над атрибутами 𝑔𝑔𝑖𝑖,1, потім операції пі-
дстановки 𝑠𝑠𝑖𝑖,1 та 𝑠𝑠𝑖𝑖,2, і в кінці – 𝑔𝑔𝑖𝑖,2.
Нетермінальний алфавіт 𝑁𝑁 = {𝛼𝛼𝑖𝑖}
складається з допоміжних символів.
Термінальний алфавіт – множина ге-
нів хромосоми, що трансформується. На-
приклад, ген швидкої передобробки QP –
передбачення позиції елемента у відсорто-
ваному масиві і перестановка, ген, який ві-
дповідає одному проходу алгоритму
сортування бульбашкою у зворотному по-
рядку – BSB. Повний перелік генів предста-
влено у [12]. Термінали ‘start’ та ‘end’
відповідають початковій і кінцевій послідо-
вностям генів вузла – ‘Start’ і ‘End’ на
рис. 1.
Кожний вузол дерева на рис. 1 має
початкову і кінцеву послідовності генів а
також вказівники на вузли-нащадки. Лист-
кові вузли мають порожні вказівники,
тобто не мають нащадків.
У процесі трансформації дерева-
хромосоми операції підстановки реалізу-
ють додавання терміналів (генів) до резуль-
туючої послідовності (масиву). Для обходу
дерева вузли додаються до допоміжної
структури – стеку, використання якого за-
мінює рекурсію.
Атрибути поточної форми:
current – вказівник на поточний
вузол дерева-хромосоми;
stack – стек вказівників на вузли де-
рева, які не були трансформовані;
stackSize – розмір стеку вказівників
на вузли дерева.
Розглянемо особливості відношень
підстановки.
При використанні відношення 𝛼𝛼 →
𝑆𝑆 ↓ 𝛽𝛽 ∙ 𝛼𝛼 у процесі конструювання 𝛽𝛽 може
бути додано до стеку S. Подальші підстано-
вки будуть продовжено для 𝛼𝛼.
Використання відношення 𝛼𝛼 →𝜏𝜏 𝛽𝛽 ↑
𝑆𝑆 ∙ 𝛼𝛼 дає можливість дістати верхній еле-
мент із стеку S і покласти його у 𝛽𝛽, якщо
атрибут доступності 𝜏𝜏 відношення підста-
новки дорівнює true.
Виконаємо конкретизацію констру-
ктора C𝐶𝐶𝐶𝐶.
𝐶𝐶𝐶𝐶𝐶𝐶 = ⟨Μ𝐶𝐶𝐶𝐶, Σ𝐶𝐶𝐶𝐶, Λ𝐶𝐶𝐶𝐶⟩ ⟼ 𝐾𝐾 𝐶𝐶𝐶𝐶𝐶𝐶𝐾𝐾
= ⟨Μ𝐶𝐶𝐶𝐶𝐾𝐾, Σ𝐶𝐶𝐶𝐶𝐾𝐾, Λ𝐶𝐶𝐶𝐶𝐾𝐾⟩ , (2)
де Μ𝐶𝐶𝐶𝐶𝐾𝐾 = Μ𝐶𝐶𝐶𝐶, Σ𝐶𝐶𝐶𝐶𝐾𝐾 = Σ𝐶𝐶𝐶𝐶, Λ𝐶𝐶𝐶𝐶𝐾𝐾 ⊃ Λ𝐶𝐶𝐶𝐶.
Інформаційне забезпечення конст-
руювання Λ𝐶𝐶𝐶𝐶𝐾𝐾 розширене наступними
правилами.
Перше правило 𝜓𝜓1 = 〈 〈𝑠𝑠1,1, 𝑠𝑠1,2〉,
〈𝑔𝑔1,1 , 𝑔𝑔1,2 〉〉 реалізує додавання кореневого
вузла дерева-хромосоми до стеку вузлів з
яких ще не були скопійовані послідовності
генів. Буде виконуватись тільки один раз на
початку процесу трансформації.
𝑠𝑠1,1 = 〈𝛼𝛼 → 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 ↓ 𝑟𝑟𝑟𝑟𝑟𝑟𝑠𝑠 ↲
𝑠𝑠ℎ𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑠𝑠𝑟𝑟𝑟𝑟𝑟𝑟 ∙ 𝛼𝛼 〉;
𝑠𝑠1,2 = 〈ε〉;
𝑔𝑔1,1 = 〈ε〉;
𝑔𝑔1,2 = 〈=: (𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑆𝑆𝑠𝑠𝑠𝑠𝑟𝑟, 1)〉
(2)
Правило 𝜓𝜓2 = 〈 〈𝑠𝑠2,1, 𝑠𝑠2,2〉, 〈𝑔𝑔2,1 ,
𝑔𝑔2,2 〉〉 реалізує діставання вузла зі стеку ву-
злів і додавання початкової і кінцевої пос-
лідовностей генів до послідовності
терміналів.
Рис. 1. Приклад хромосоми у вигляді
дерева
Програмна інженерія – прикладні методи
43
𝑠𝑠2,1 = 〈𝛼𝛼 →𝜏𝜏1 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 ↑ 𝑠𝑠𝑐𝑐𝑠𝑠𝑐𝑐𝑠𝑠 ∙ 𝛼𝛼 〉;
𝑠𝑠2,2 = 〈𝜌𝜌 → 𝑠𝑠𝑐𝑐𝑠𝑠𝑐𝑐𝑐𝑐 ↲ 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 ∙ 𝜌𝜌 ∙
𝑐𝑐𝑐𝑐𝑒𝑒 ↲ 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 〉;
𝑔𝑔2,1 = 〈
> (𝑓𝑓1, stackSize, 0),
== (𝑓𝑓2, 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐, 𝑐𝑐𝑐𝑐𝑛𝑛𝑛𝑛),
∧ (τ1, 𝑓𝑓1, 𝑓𝑓2)
〉 ;
𝑔𝑔2,2 = 〈−(𝑠𝑠𝑐𝑐𝑠𝑠𝑐𝑐𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑐𝑐, 𝑠𝑠𝑐𝑐𝑠𝑠𝑐𝑐𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑐𝑐, 1)〉
(3)
Третє правило 𝜓𝜓3 = 〈 〈𝑠𝑠3,1, 𝑠𝑠3,2〉,
〈𝑔𝑔3,1 , 𝑔𝑔3,2 〉〉 реалізує додавання вузлів на-
щадків поточного вузла до стеку. У подаль-
шому вузли будуть діставатись зі стеку у
зворотному порядку, тому спочатку дода-
ється правий, а потім лівий вузол.
𝑠𝑠3,1 =
〈𝛼𝛼 →𝜏𝜏1 𝑠𝑠𝑐𝑐𝑠𝑠𝑐𝑐𝑠𝑠 ↓ 𝑐𝑐𝑠𝑠𝑔𝑔ℎ𝑐𝑐 ↲ 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 ∙ 𝛼𝛼
𝛼𝛼 →𝜏𝜏1 𝑠𝑠𝑐𝑐𝑠𝑠𝑐𝑐𝑠𝑠 ↓ 𝑛𝑛𝑐𝑐𝑓𝑓𝑐𝑐 ↲ 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 ∙ 𝛼𝛼
〉 ;
𝑠𝑠3,2 = 〈ε〉;
𝑔𝑔3,1 = 〈! = (τ1, 𝑛𝑛𝑐𝑐𝑓𝑓𝑐𝑐 ↲
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐, 𝑐𝑐𝑐𝑐𝑛𝑛𝑛𝑛)〉;
𝑔𝑔3,2 = 〈+(𝑠𝑠𝑐𝑐𝑠𝑠𝑐𝑐𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑐𝑐, 𝑠𝑠𝑐𝑐𝑠𝑠𝑐𝑐𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑐𝑐, 2)
=: (𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐, 𝑐𝑐𝑐𝑐𝑛𝑛𝑛𝑛) 〉
(4)
Початкові умови конструювання:
хромосома деревоподібної структури, де у
кожного вузла є початкова і кінцева послі-
довності генів, і всі вузли, окрім листових,
мають два вузли-нащадки.
Таблиця 1.
Приклад використання стеку у процесі
трансформації хромосоми
Стек ву-
злів
Вузол,
який діс-
тається зі
стеку
Вузол, з якого
копіюються гени
і нащадки дода-
ються до стеку
[1]
[] 1
[5,2] 1
[5] 2
[5,4,3] 2
[5,4] 3
[5,4] 3
[5] 4
[5] 4
[] 5
[7,6] 5
[7] 6
[7] 6
[] 7
[] 7
У табл. 1 представлений процес об-
ходу дерева з використанням стеку. Числа
у таблиці відповідають номерам вузлів на
рис. 1. Вузли будуть опрацьовані у насту-
пній послідовності: 1, 2, 3, 4, 5, 6, 7.
Результатом трансформації буде
наступна послідовність генів: [PUA, QP,
BSF, BSF, SIS, PUA, BLPM, FSS, FSS, P,
PUA, BSF, SR, FSS, FS, ESS, BGPM, FSS,
FSB, FS, ESS, ESS, PUA, SR, BSB, BGQP,
P, PUA, BSF, SR, FSS, FS, ESS, PUA,
BLQP, FSB, BSB, FS, ESS, ESS, ESS].
Конструктор формування тексту
програм
Конструктор формування тексту
програм (теж конструктор-трансформер)
перетворює послідовність генів на текст
програми обраною мовою програмування
(у даній роботі – С++).
Визначимо спеціалізацію констру-
тора C𝑃𝑃𝑃𝑃 – моделі декодування послідовно-
сті генів, що кодує алгоритм сортування, у
текст програми:
𝐶𝐶 = ⟨Μ, Σ, Λ⟩ ⟼𝑠𝑠 𝐶𝐶𝑃𝑃𝑃𝑃
= ⟨Μ𝑃𝑃𝑃𝑃, Σ𝑃𝑃𝑃𝑃, Λ𝑃𝑃𝑃𝑃⟩, (5)
де Μ𝑃𝑃𝑃𝑃 – носій, що включає термінальний
(𝑇𝑇𝑃𝑃𝑃𝑃) і нетермінальний (𝑁𝑁𝑃𝑃𝑃𝑃) алфавіт, а та-
кож множину правил продукції Ψ з прави-
лами 𝜓𝜓𝑖𝑖 = 〈𝑠𝑠i , 𝑔𝑔i 〉 ∈ Ψ, де i – номер
правила, 𝑠𝑠i – послідовність відношень під-
становки, 𝑔𝑔i – послідовність операцій над
атрибутами. Σ𝑃𝑃𝑃𝑃 – операції та відносини на
елементах Μ𝑃𝑃𝑃𝑃. ІЗК Λ𝑃𝑃𝑃𝑃 ⊃ Λ.
Нетермінали – гени хромосоми, яка
кодує алгоритм сортування.
Термінали – текстові фрагменти
програм обраною мовою програмування,
які відповідають частинам відомих алгори-
тмів сортування, передобробок і допоміж-
них функцій, і кодуються генами. Від-
повідно до гена X будемо використовувати
термінал TX. Наведемо список усіх терміна-
лів: 𝑇𝑇S , 𝑇𝑇E , 𝑇𝑇B𝑆𝑆𝑃𝑃 , 𝑇𝑇B𝑆𝑆𝑆𝑆 , 𝑇𝑇F𝑆𝑆𝑆𝑆 , 𝑇𝑇F𝑆𝑆𝑆𝑆 , 𝑇𝑇S𝐸𝐸𝐸𝐸𝐸𝐸 ,
𝑇𝑇SE𝐸𝐸 , 𝑇𝑇SI𝑆𝑆 , 𝑇𝑇P , 𝑇𝑇FS , 𝑇𝑇P𝑈𝑈𝑈𝑈 , 𝑇𝑇E𝑆𝑆S , 𝑇𝑇M𝐿𝐿 , 𝑇𝑇M𝑅𝑅 ,
𝑇𝑇Q𝑃𝑃 , 𝑇𝑇P𝑀𝑀 , 𝑇𝑇SR , 𝑇𝑇B𝐿𝐿𝐿𝐿𝑃𝑃 , 𝑇𝑇B𝐿𝐿𝑃𝑃𝑀𝑀 , 𝑇𝑇B𝐺𝐺𝐿𝐿𝑃𝑃 , 𝑇𝑇B𝐺𝐺𝑃𝑃𝑀𝑀 .
Усі термінали 𝑇𝑇∗ ∈ 𝑇𝑇𝑃𝑃𝑃𝑃 мають атри-
бут 𝑐𝑐𝑐𝑐𝑒𝑒𝑐𝑐 ↲ 𝑇𝑇∗ – текст програми відповідний
алгоритму, який кодується геном.
Програмна інженерія – прикладні методи
44
Атрибути терміналів 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇S і
𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇E є незмінними (для любого сфор-
мованого алгоритму) частинами тексту
програми, які додаються відповідно на по-
чатку і в кінці файлу. На початку (𝑇𝑇S ) вклю-
чаються заголовкові файли із допоміжними
функціями і типами даних, оголошуються
допоміжні структури, початок реалізації
функції сортування. Кінцева частина (𝑇𝑇E )
включає код злиття усіх пар із стеку відсо-
ртованих масивів для злиття.
Наступні термінали включають пе-
ревірку флагу відсортованості, оновлення
значень змінних, що входять до глобаль-
ного контексту, і код програми відповідно
до:
TBSF – одного проходу сортуванням
бульбашкою в прямому напрямку;
TBSB – одного проходу сортуванням
бульбашкою у зворотному напря-
мку;
TFSB – пошуку найбільшого елеме-
нта у невідсортованій частині ма-
сиву і перестановка на поточне
місце;
TFSS – пошуку найменшого елемента
у невідсортованій частині масиву і
перестановка на поточне місце;
TSEEI – вставки поточного елемента
у відсортовану частину у кінці ма-
сиву;
TSEI – вставки поточного елемента у
відсортовану частину на початку ма-
сиву;
TQP – швидкої передобробки;
TPM – передобробки із пам’яттю;
TSR – передобробки із розворотом;
TBLQP – блочної локальної швидкої
передобробки;
TBLPM – блочної локальної передоб-
робки з пам’яттю;
TBGQP – блочної глобальної швидкої
передобробки;
TBGPM – блочної глобальної передоб-
робки з пам’яттю.
Вказані передобробки викладені в
[10].
Атрибут 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇SI𝑆𝑆 представляє
текст програми, який розділяє масив на дві
частини, зберігає вказівники і розміри у
стеку невідсортованих підмасивів (для по-
дальшого окремного сортування) і у стеку
масивів, для яких виконуватиметься злиття
у кінці конструйованої функції.
Атрибут 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇P є текстом, який
обирає елемент, переставляє менші і більші
елементи відповідно зліва і справа, зберігає
вказівники і розміри частин масиву для по-
дальшого сортування.
𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇FS – атрибут, який є текстом
загальновідомого алгоритму сортування. У
поточній роботі використовується текст
швидкого сортування.
Атрибути 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝑃𝑃𝑈𝑈𝑈𝑈 і 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝐸𝐸𝑆𝑆𝑆𝑆
представляють код допоміжних функцій.
Перший дістає невідсортований масив зі
стеку невідсортованих масивів для подаль-
шого сортування. Другий додає закриті фі-
гурні дужки до тексту програми у кількості,
потрібній для успішної компіляції про-
грами.
Атрибути терміналів 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝑀𝑀𝐿𝐿 і
𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝑀𝑀𝑀𝑀 містять код, який оновлює зна-
чення змінних із глобального контексту і
додає до стеку масивів для подальшого
злиття відсортований підмасив (відповідно
зліва і справа) та решту масиву.
Результатом закінчення конструю-
вання буде цілісний текст програми, який
включає конструйовану функцію сорту-
вання, допоміжні структури і функції.
Виконаємо конкретизацію констру-
ктора 𝐶𝐶𝑃𝑃𝑃𝑃:
𝐶𝐶𝑃𝑃𝑃𝑃 = ⟨Μ𝑃𝑃𝑃𝑃, Σ𝑃𝑃𝑃𝑃, Λ𝑃𝑃𝑃𝑃⟩ ⟼ 𝐾𝐾 𝐶𝐶𝑃𝑃𝑃𝑃𝐾𝐾
= ⟨Μ𝑃𝑃𝑃𝑃𝐾𝐾, Σ𝑃𝑃𝑃𝑃𝐾𝐾, Λ𝑃𝑃𝑃𝑃𝐾𝐾⟩ , (6)
де Μ𝑃𝑃𝑃𝑃𝐾𝐾 = Μ𝑃𝑃𝑃𝑃, Σ𝑃𝑃𝑃𝑃𝐾𝐾 = Σ𝑃𝑃𝑃𝑃 ∪ {+, ∶=, ↓, ↑},
Λ𝑃𝑃𝑃𝑃𝐾𝐾 ⊃ Λ𝐶𝐶𝐶𝐶.
Визначені наступні операції над ат-
рибутами: +(a, b, c) – додавання аргументів
b і c, результат зберігається у a; :=(a, b) –
Програмна інженерія – прикладні методи
45
присвоєння значення b змінній a; ↓(a, b) –
додає елемент b у стек a; ↑(a, b) – дістає вер-
хній елемент із стеку a, зберігає його зна-
чення у b.
Інформаційне забезпечення Λ𝑃𝑃𝐹𝐹𝐾𝐾
збагачено наступними положеннями.
Атрибути терміналів і нетерміналів
поточної форми: nBrackets – поточна кіль-
кість відкритих фігурних дужок, відповідна
кількість закритих дужок буде додана атри-
бутом 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ E𝑆𝑆𝑆𝑆 для успішної компіляції
коду програми; closingBrackets – стек лічи-
льників відкритих фігурних дужок, верхній
елемент відповідає поточній області види-
мості.
Початкові умови конструювання:
послідовність (масив) генів, які кодують ча-
стини алгоритмів сортування і допоміжні
операції.
Умови завершення конструювання:
сформована програма сортування (поточна
форма не містить нетерміналів).
Перше правило 𝜓𝜓1 = 〈 〈𝑠𝑠1,1, 𝑠𝑠1,2〉,
〈𝑔𝑔1,1 , 𝑔𝑔1,2 〉〉 виконує підстановку постійної
частини коду, однакової для усіх програм.
Операції над атрибутами не виконуються.
𝑠𝑠1,1 = 〈𝜎𝜎 → 𝛾𝛾 〉;
𝑠𝑠1,2 = 〈𝛼𝛼 → 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝑠𝑠 ∙ 𝛼𝛼 ∙ 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲
𝑇𝑇𝑒𝑒〉;
𝑔𝑔1,1 = 〈ε〉; 𝑔𝑔1,2 = 〈ε〉
(7)
Для 𝛼𝛼 будуть продовжені підстано-
вки.
Наступне правило 𝜓𝜓2 містить від-
ношення підстановки програмного коду
для гена PUA.
𝑠𝑠2,1 = 〈𝜎𝜎 → 𝛼𝛼 〉;
𝑠𝑠2,2 = 〈𝛼𝛼 → 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝑃𝑃𝑃𝑃𝑃𝑃 ∙ 𝛼𝛼 〉;
𝑔𝑔2,1 = 〈ε〉;
𝑔𝑔2,2 = 〈↓ (closingBrackets , 0)〉
(8)
Операції над атрибутами додають
новий елемент до стеку лічильників фігу-
рних дужок. Наступні операції над атри-
бутами, які збільшують лічильник
фігурних дужок, будуть збільшувати
останню додану змінну.
Правило 𝜓𝜓3 містить відношення пі-
дстановки програмного коду для гена
ESS.
𝑠𝑠3,1 = 〈𝜎𝜎 → 𝛼𝛼 〉;
𝑠𝑠3,2 = 〈𝛾𝛾 → 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝐸𝐸𝐸𝐸𝐸𝐸 ∙ 𝛾𝛾 〉;
𝑔𝑔3,1 = 〈ε〉;
𝑔𝑔3,2 = 〈↑ (𝑐𝑐𝑐𝑐𝑐𝑐𝑠𝑠𝑐𝑐𝑐𝑐𝑔𝑔𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑒𝑒𝑡𝑡𝑠𝑠,
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑒𝑒𝑡𝑡𝑠𝑠)〉
(9)
Програмний код, що кодується ге-
ном ESS, виконує додавання фігурних
дужок, що закриваються у кількості, рів-
ній значенню атрибута nBrackets. Це пот-
рібно для закриття областей видимості,
відкритих додаванням попередніх фраг-
ментів тексту програм.
Правило 𝜓𝜓4 містить відношення пі-
дстановки для додавання програмного
коду, що відповідає генам, які відкрива-
ють нову область видимості і збільшують
лічильник дужок, які необхідно закрити.
Для мінімізації кількості правил позна-
чимо символом Ter* будь-який термінал-
ген із множини {FSB, FSS, SEEI, SEI,
BSB, BSF, P, QP, PM, SR, BLQP, BLPM,
BGQP, BGPM}.
𝑠𝑠4,1 = 〈𝛾𝛾 → 𝑇𝑇𝑒𝑒𝑐𝑐∗ ∙ 𝛾𝛾 〉;
𝑠𝑠4,2 = 〈𝛼𝛼 → 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝑒𝑒𝑐𝑐∗ ∙ 𝛼𝛼 〉;
𝑔𝑔4,1 = 〈ε〉;
𝑔𝑔4,2
= 〈+(𝑡𝑡𝑐𝑐𝑡𝑡 ↲ closingBrackets ,
𝑡𝑡𝑐𝑐𝑡𝑡 ↲ closingBrackets , 1) 〉
(10)
Правило 𝜓𝜓5 містить відношення пі-
дстановки для додавання програмного
коду, що відповідає генам, які не відкри-
вають нову область видимості. Позна-
чимо символом 𝑇𝑇𝑒𝑒𝑐𝑐∗∗ будь-який термінал-
ген із множини {SIS, ML, MR, FS}.
𝑠𝑠5,1 = 〈𝛾𝛾 → 𝑇𝑇𝑒𝑒𝑐𝑐∗∗ ∙ 𝛾𝛾 〉;
𝑠𝑠5,2 = 〈𝛼𝛼 → 𝑡𝑡𝑒𝑒𝑒𝑒𝑡𝑡 ↲ 𝑇𝑇𝑒𝑒𝑐𝑐∗∗ ∙ 𝛼𝛼 〉;
𝑔𝑔5,1 = 〈ε〉;
𝑔𝑔5,2 = 〈ε〉
(11)
Результатом конструювання функції
сортування буде не тільки текст безпосере-
дньо функції сортування, а й текстове пред-
ставлення коду всього файлу реалізації
(.cpp). Відповідний заголовковий файл (.h)
не змінюється залежно від хромосоми і
створюється заздалегідь. Він включає ого-
лошення функції сортування, що констру-
юється і має наступний вигляд:
#pragma once
void ConstructedSort(int* arr, int n);
Програмна інженерія – прикладні методи
46
Відповідний файл реалізації склада-
ється із двох частин: незмінної частини і ре-
алізації функції сортування, що
конструюється із хромосоми. У незмінній
частині включається вищезгаданий заголо-
вковий файл та заголовкові файли із допо-
міжними утилітами і типами даних.
Оголошуються допоміжні структури і фун-
кції. І початок саме реалізації функції сор-
тування, що конструюється, де оголо-
шуються усі змінні-атрибути із початко-
вими значеннями. Початкова незмінна час-
тина файлу реалізації, яка відповідає
терміналу 𝑇𝑇𝑆𝑆, має наступний вигляд (код у
статті відрізняється форматуванням від
коду програми, для економії місця):
// 𝒕𝒕𝒆𝒆𝒆𝒆𝒕𝒕 ↲ 𝑻𝑻𝑺𝑺:
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
#include "Sort/Sort.h"
#include "Utilities/Utilities.h"
void Merge(int* arr, int size1, int size2) {
std::vector<int> tempArray1;
tempArray1.assign(arr, arr + size1);
int indexOfMergedArray = 0; // Index of
the first element in the merged array
int indexOfSubArrayOne = 0; // Index of
the first element in the first sub-array
int indexOfSubArrayTwo = 0; // Index of
the first element in the second sub-array
while (indexOfSubArrayOne < size1 &&
indexOfSubArrayTwo < size2) {
if (tempArray1[indexOfSubArrayOne] <
arr[ size1 + indexOfSubArrayTwo]) {
arr[indexOfMergedArray] =
tempArray1[indexOfSubArrayOne];
indexOfSubArrayOne++;
} else {
arr[indexOfMergedArray] = arr[ size1
+ indexOfSubArrayTwo];
indexOfSubArrayTwo++; }
indexOfMergedArray++; }
while (indexOfSubArrayOne < size1) {
arr[indexOfMergedArray] =
tempArray1[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++; }
while (indexOfSubArrayTwo < size2) {
arr[indexOfMergedArray] = arr[size1 +
indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++; }}
template <typename T>
struct SubarrayInfo {
T* Arr = nullptr;
int Size1;
int Size2; };
void ConstructedSort(int* arr, int n) {
const int minBlockSize = 32,
maxBlockSize = 10000;
std::stack<SubarrayInfo<int>>
subarraysToMerge;
std::stack<std::pair<int*, int>>
unsortedArrays;
int size1 = 0, size2 = 0, start = 1, end =
0, localSize = 0;
bool swapped = false;
int s = 0, e = n – 1, idx = 0;
bool isSorted = false;
auto pivotIdx = (s + e) / 2;
int min, max;
Текст програми відповідний поточ-
ній хромосомі буде додано між початковою
і кінцевою незмінними частинами. Далі
представлено кінцеву незмінну частину,
якій відповідає термінал 𝑇𝑇𝐸𝐸, у якій гаранто-
вано відбувається злиття усіх відсортова-
них частин масиву і закриття останньої
фігурної дужки функції.
// 𝒕𝒕𝒆𝒆𝒆𝒆𝒕𝒕 ↲ 𝑻𝑻𝑬𝑬:
while(!subarraysToMerge.empty()) {
Програмна інженерія – прикладні методи
47
const auto& stm =
subarraysToMerge.top();
subarraysToMerge.pop();
Merge(stm.Arr, stm.Size1, stm.Size2);
}}
У результаті буде сформований го-
товий текст програми. Можливе як дода-
вання файлів із сформованим кодом
сортування до файлів програми, так і ком-
піляція, і збірка окремої мінімалістичної
бібліотеки.
Для перевірки спроможності адап-
тованих алгоритмів конкурувати з відо-
мими алгоритмами сортування виконані
експерименти із застосуванням запропо-
нованого конструктивно-продукційного
підходу на основі генетичного алгоритму.
Експериментальні дослідження
Експерименти проводились над даними
різної структури:
повністю відсортовані дані;
дані, відсортовані у зворотному по-
рядку;
повністю відсортований масив, у
якому виконується декілька перес-
тановок пар елементів, вибраних ви-
падковим чином;
відсоток невідсортованості. У повні-
стю відсортованому масиві випадко-
вим чином обирається певна
кількість послідовних ділянок еле-
менів сумарною довжиною рівною
даному відсотку довжини усього ма-
сиву. В межах кожної ділянки випа-
дково обрані елементи міняються
місцями певну кількість разів;
повністю випадкові дані.
Проведені експерименти із вищеза-
значеними типами даних обсягом один
мільйон і десять мільйонів елементів.
Для кожної популяції генетичного
алгоритму генерувався 51 масив сортова-
них даних відповідної структури. Вони збе-
рігались у 51 бінарний файл. Кожний
індивід популяції, який представляє собою
конкретний алгоритм сортування, вичиту-
вав масив даних із файла. Виконувалось со-
ртування, перевірялось, чи сортування ви-
конане успішно і чи зберігався результат –
час виконання – у масив. Після сортування
усіх масивів вхідних даних вираховувався
медіанний час і зберігався у окремий бінар-
ний файл. Таким чином використовувались
ідентичні дані для кожного індивіда.
Під час формування наступної попу-
ляції, 20% хромосом переносились з попе-
редньої, 40% - додавалися після схре-
щування, решта заповнювалась новими
хромосомами.
Задля обмеження довжини хромо-
соми і, відповідно, довжини генерованої
функції сортування, процес генерації хро-
мосоми керувався за допомогою наступних
параметрів. Параметр MGBS = 1 визначає
мінімальну кількість генів, необхідну для
того, щоб стали доступними для вибору
гени розбиття, які додають нові вузли-на-
щадки до поточного вузла. Максимальна
глибина дерева-хромосоми MD = 3. На по-
чатку генерації хромосоми для кореневого
вузла глибина дорівнювала одиниці. При
виборі гена розбиття масиву до поточного
вузла додавались два вузли-нащадки із гли-
биною більшою, ніж у поточного вузла на
одиницю. У разі глибини меншій, ніж мак-
симальна, правило вибору гена фінального
сортування недоступне. Натомість досту-
пні правила вибору генів розбиття. При до-
сягненні максимальної глибини замість
гену розбиття масива підставляється ген фі-
нального сортування і вузли нащадки не до-
даються. Таким чином будується
збалансоване дерево-хромосома із заданою
глибиною.
Результати експериментів наведені
у табл. 2. У рядку із відповідним типом да-
них представлений кращий із загальновідо-
мих алгоритмів і кращий із конструйованих
(адаптованих).
Для повністю відсортованих даних
покращення становить 35-37% порівняно з
кращим із загальновідомих алгоритмів, а
саме сортуванням вставками. Для даних
відсортованих у зворотному порядку, конс-
труйовані алгоритми показали найвищий
рівень покращення – 92-94%. Це досяга-
ється наявністю гена SR на початку хромо-
соми.
Програмна інженерія – прикладні методи
48
Таблиця 2. Результати експериментів із сортування
Обсяг
сорто-
ваних
даних
Тип вхід-
них даних
Алгоритм Медіан-
ний час,
мкс
Покра-
щення/По
гіршення,
%
Один
міль-
йон
Повністю
відсорто-
вані
BSB_FSB_FSB_P_PUA_SEEI_MR_P_PUA_BGQP_
BSB_BSF_FS_ESS_PUA_QP_FSB_BLQP_SEEI_MR
_FS_ESS_ESS_PUA_BSF_BSF_QP_SEI_ML_SIS_P
UA_FSB_FS_ESS_PUA_QP_SEI_ML_FS_ESS_ESS
_ESS
329 37.33%
InsertionSort 525
Відсорто-
вані у зво-
ротному
порядку
SR_SEI_ML_FSS_BGPM_SIS_PUA_BSF_BSF_BLP
M_FSB_P_PUA_SEI_ML_FSS_QP_FS_ESS_PUA_B
SF_SEEI_MR_SEEI_MR_FS_ESS_ESS_PUA_BSF_
QP_P_PUA_SEEI_SEEI_MR_BSF_SEI_ML_FS_ESS
_PUA_FSB_SEI_ML_FS_ESS_ESS_ESS
896 92.7%
QuickSort 12276
Декілька
переста-
новок
InsertionSort 2562 -484%
P_PUA_P_PUA_FS_ESS_PUA_FS_ESS_ESS_PUA_
P_PUA_FS_ESS_PUA_FS_ESS_ESS_ESS
14985
Відсоток
невідсор-
тованих
елементів
P_PUA_P_PUA_FS_ESS_PUA_FS_ESS_ESS_PUA_
P_PUA_FS_ESS_PUA_FS_ESS_ESS_ESS
17847 3.41%
QuickSort 18475
Випадкові P_PUA_P_PUA_FS_ESS_PUA_FS_ESS_ESS_PUA_
P_PUA_FS_ESS_PUA_FS_ESS_ESS_ESS
61831 0.24%
QuickSort 61980
Де-
сять
міль-
йонів
Повністю
відсорто-
вані
BSF_SEEI_MR_SIS_PUA_SEEI_MR_BGQP_BSF_P
_PUA_BSF_BSB_BSF_FSS_FS_ESS_PUA_SR_FS_
ESS_ESS_PUA_SEEI_MR_PM_SIS_PUA_QP_FS_E
SS_PUA_BLPM_SEEI_SEEI_MR_SR_FS_ESS_ESS
_ESS
3706 35.06%
InsertionSort 5707
Відсорто-
вані у зво-
ротному
порядку
SR_BSF_P_PUA_FSB_SIS_PUA_FSS_BSB_FSB_Q
P_FS_ESS_PUA_FSB_SEI_SEEI_ML_MR_QP_FS_E
SS_ESS_PUA_BSF_SR_P_PUA_SR_BSF_BLQP_FS
S_FS_ESS_PUA_BSF_BSF_BSF_SEI_ML_FS_ESS_
ESS_ESS
8364 94.07%
QuickSort 141151
Декілька
переста-
новок
P_PUA_P_PUA_FS_ESS_PUA_FS_ESS_ESS_PUA_
P_PUA_FS_ESS_PUA_FS_ESS_ESS_ESS
193621 0.137%
QuickSort 193887
Відсоток
невідсор-
тованих
елементів
P_PUA_P_PUA_FS_ESS_PUA_FS_ESS_ESS_PUA_
P_PUA_FS_ESS_PUA_FS_ESS_ESS_ESS
201806 0.033%
QuickSort 201872
Випадкові SIS_PUA_SIS_PUA_FS_ESS_PUA_FS_ESS_ESS_P
UA_SIS_PUA_FS_ESS_PUA_FS_ESS_ESS_ESS
715804 0.322%
QuickSort 718110
Програмна інженерія – прикладні методи
49
Сортування масивів із кількома пе-
рестановками обсягом один мільйон елеме-
нтів показало значне погіршення – 484%.
Для даних обсягом десять мільйонів наявне
незначне покращення – 0.137%. Варто за-
значити, що на масивах обсягом один міль-
йон сортування вставками показало значну
ефективність, однак для десяти мільйонів
елементів кращим із загальновідомих ви-
явилось швидке сортування.
Для експериментальних даних із від-
сотком невідсортованих елементів пока-
щення становить 0.33% (десять мільйонів) і
3.41% (один мільйон).
Покращення для сортування випад-
кових даних обсягом один мільйон стано-
вить 0.24%. Конструйований алгоритм
включає гени розбиття із перестановкою
елементів, що відповідають частині логіки
швидкого сортування. Для даних обсягом
десять мільйонів розраховане покращення
0.32%. Конструйонавий алгоритм включає
гени розбиття, які відповідають частинам
сортування злиттям.
Висновки
У попередніх роботах була запропо-
нована конструктивна модель хромосоми
деревовидної структури яка кодує алгоритм
сортування. Викладена спеціалізація та
конкретизація конструктору формування
хромосом.
У цій статті як логічне продовження
попередньої роботи розроблено підхід до
декодування хромосом у послідовність ге-
нів і їх подальшого перетворення на текст
програми мовою програмування.
Застосування конструктивно‑проду-
кційного моделювання є ефективним підхо-
дом до побудови алгоритмів, здатних
адаптивно формувати структуру рішення
на основі чітко визначених продукційних
правил та конструктивних принципів. За-
пропонований метод дав змогу системно
описати процес створення алгоритмів як
послідовність перетворень, у межах яких
кожне правило робило внесок у форму-
вання цілісного алгоритму сортування.
Продемонстровано ефективність за-
стосування генетичного алгоритму для
структурної адаптації конструйованих алго-
ритмів сортування і вибору найбільш прис-
тосованого до заданих умов використання.
Проведені експерименти підтвердили, що
еволюційний підхід здатний адаптивно вдо-
сконалювати структуру алгоритму, посту-
пово підвищуючи його продуктивність.
Література
1. R. Sedgewick, ‘Implementing quicksort
programs’, Communications of the ACM,
21(10), 847–857 (1978).
2. D. E. Knuth. Sorting by Exchanging. The Art
of Computer Programming. – Vol. 3: Sorting
and Searching. – 1st ed. – Addison-Wesley. –
pp. 110–111. – 1973
3. J. W. J. Williams, Algorithm 132 (heapsort),
Communications of the ACM, 7, 347–348
(1964)
4. C. Song and H. Li, “Improvement of Counting
Sorting Algorithm,” in Journal of Computer
and Communications, vol. 11, pp. 12–22, 2023
5. J. Wassenberg and P. Sanders, “Engineering a
multi‑core radix sort,” in Proc. Euro‑Par 2011,
Part II, LNCS 6853, Bordeaux, France, 2011, pp.
160–169. doi: 10.1007/978‑3‑642‑23397‑5_16.
6. N. Faujdar and S. Saraswat, “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
7. B. Haeupler, R. Hladík, J. Iacono, V. Rozhoň, R.
E. Tarjan and J. Tětek, “Fast and Simple Sorting
Using Partial Information,” in Proceedings of the
2025 Annual ACM‑SIAM Symposium on
Discrete Algorithms (SODA), pp. 3953–3973,
2025, doi: 10.1137/1.9781611978322.134
8. M. Subramaniam, T. Tripathi and O.
Chandraumakantham, “Cluster Sort: A Novel
Hybrid Approach to Efficient In-Place Sorting
Using Data Clustering,” in IEEE Access, vol.
13, pp. 74359–74374, 2025.
9. В.І. Шинкаренко, А.Ю. Дорошенко, О.А.
Яценко, В.В. Разносілін, К.К. Галанін, Дво-
компонентні алгоритми сортування, Про-
блеми програмування, 2022, № 3-4. С. 32-
41. doi: 10.15407/pp2022.03-04.032.
10. В.І. Шинкаренко, О.В. Макаров, Дослі-
дження ефективності деяких детермінова-
них методів передобробки сортування
даних, Проблеми програмування, 2023, №
4, С. 3-14. doi: 10.15407/pp2023.04.003.
11. V.I. Shinkarenko, O.V. Makarov, Structural
Adaptation of Sorting Algorithms Based on
Constructive Fragments, CEUR Workshop
Proceedings. – Vol. 3806. – pp. 16–29. – 2024
Програмна інженерія – прикладні методи
50
12. В.І. Шинкаренко, О.В. Макаров Конструк-
тивно-продукційне моделювання хромосом
генетичного алгоритму з закодованими ал-
горитмами сортування, Проблеми програ-
мування, 2025, № 3, С. 39-52. doi:
10.15407/pp2025.03.039
13. D. Beasley, D. R. Bull and R. R. Martin, “An
Overview of Genetic Algorithms: Part 1,
Fundamentals,” in University Computing, vol.
15, pp. 58–69, 1993
14. В.І. Шинкаренко, В.М. Ільман. Конструкти-
вно-продукційні структури та їх граматичні
інтерпретації. I. Узагальнена формальна
конструктивно-продукційна структура . Кі-
бернетика і системний аналіз. – 2014. – Т.
50, № 5. – С. 8–16
References
1. R. Sedgewick, ‘Implementing quicksort
programs’, Communications of the ACM,
21(10), 847–857 (1978).
2. D. E. Knuth. Sorting by Exchanging. The Art
of Computer Programming. – Vol. 3: Sorting
and Searching. – 1st ed. – Addison-Wesley. –
pp. 110–111. – 1973
3. J. W. J. Williams, Algorithm 132 (heapsort),
Communications of the ACM, 7, 347–348
(1964).
4. C. Song and H. Li, “Improvement of Counting
Sorting Algorithm,” in Journal of Computer
and Communications, vol. 11, pp. 12–22, 2023
5. J. Wassenberg and P. Sanders, “Engineering a
multi‑core radix sort,” in Proc. Euro‑Par 2011,
Part II, LNCS 6853, Bordeaux, France, 2011, pp.
160–169. doi: 10.1007/978‑3‑642‑23397‑5_16.
6. N. Faujdar and S. Saraswat, “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
7. B. Haeupler, R. Hladík, J. Iacono, V. Rozhoň, R.
E. Tarjan and J. Tětek, “Fast and Simple Sorting
Using Partial Information,” in Proceedings of the
2025 Annual ACM‑SIAM Symposium on
Discrete Algorithms (SODA), pp. 3953–3973,
2025, doi: 10.1137/1.9781611978322.134
8. M. Subramaniam, T. Tripathi and O.
Chandraumakantham, “Cluster Sort: A Novel
Hybrid Approach to Efficient In-Place Sorting
Using Data Clustering,” in IEEE Access, vol.
13, pp. 74359–74374, 2025.
9. V. I. Shinkarenko, A. Yu. Doroshenko, O. A.
Yatsenko, V. V. Raznosilin, K. K. Galanin.
Bicomponent sorting algorithms. Problems of
Programming. – 2022. – No. 3–4. – pp. 32–41.
– DOI: 10.15407/pp2022.03-04.032
10. V. I. Shinkarenko, O. V. Makarov. Study of the
effectiveness of some deterministic
preprocessing methods of data sorting.
Problems of Programming. – 2023. – No. 4. –
pp. 3–14. – DOI: 10.15407/pp2023.04.003
11. V.I. Shinkarenko, O.V. Makarov, Structural
Adaptation of Sorting Algorithms Based on
Constructive Fragments, CEUR Workshop
Proceedings. – Vol. 3806. – pp. 16–29. – 2024
12. V. I. Shinkarenko, O. V. Makarov. Constructive-
synthesizing modeling of the genetic algorithm
chromosomes with encoded sorting algorithms,
Problems of Programming. – 2025. – No. 3. – pp.
39–52. – DOI: 10.15407/pp2025.03.039
13. D. Beasley, D. R. Bull and R. R. Martin, “An
Overview of Genetic Algorithms: Part 1,
Fundamentals,” in University Computing, vol.
15, pp. 58–69, 1993
14. V. I. Shynkarenko, V. M. Ilman. Constructive-
Synthesizing Structures and Their
Grammatical Interpretations. I. Generalized
Formal Constructive-Synthesizing Structure.
Cybernetics and Systems Analysis. – Vol. 50,
No. 5. – pp. 8–16
Дата першого надходження до видання:
09.03.2026
Внутрішня рецензія отримана: 13.03.2026
Зовнішня рецензія отримана: 14.03.2026
Дата прийняття статті до друку: 19.03.2026
Дата публікації: 16.04.2026
Про авторів:
Шинкаренко Віктор Іванович,
доктор технічних наук, професор
Shynkarenko Victor,
Ph.D (doctor), professor
https://orcid.org/0000-0001-8738-7225
E-mail: shinkarenko_vi@ua.fm
Макаров Олексій Вікторович, аспірант
Makarov Olexiy, Post-graduate student
https://orcid.org/0009-0003-0921-155X
E-mail: makarovov@hotmail.com
Місце роботи авторів:
Український державний університет
науки і технологій,
49010, Україна, Дніпро,
вул. академіка Лазаряна, 2.
Ukrainian State University of Science and
Technology (Dnipro)
E-mail: office@ust.edu.ua
|
| id | pp_isofts_kiev_ua-article-890 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-04-24T01:00:15Z |
| publishDate | 2026 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/59/94373bed01f4cad7f6daa9dc702b3359.pdf |
| spelling | pp_isofts_kiev_ua-article-8902026-04-23T22:26:13Z Constructive-synthesizing production of sorting programs adapted by genetic algorithm Конструктивно-продукційне формування програм сортування, адаптованих генетичним алгоритмом Shynkarenko, V.I. Makarov, O.V. constructive-synthesizing modeling; sorting algorithm; time efficiency; genetic algorithm; software; information technology UDC 004.4 конструктивно-продукційне моделювання; алгоритми сортування; часова ефективність; генетичний алгоритм; програмне забезпечення; інформаційні технології УДК004.4 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 Упопередніхроботах представлені механізми конструктивно-продукційного моделювання для адаптації алгоритмів сортування. У зв’язку з цим виникли задачі перетворення хромосом генетичного алгоритму на текст програм сортування для подальшого застосування, оцінки можливостей еволюційного розвитку. Розглядається підхід до перетворення хромосом, що кодують алгоритми сортування на тексти програм готових до застосування у реальних умовах. Розроблено конструктор-трансформер, який реалізує пере творення хромосоми-дерева на лінійну послідовність генів. Інший конструктор-трансформер призначе ний для перетворення послідовності генів на код програми сортування. Наведено приклади послідовності обходу дерева-хромосоми, додавання генів до лінійної послідовності і формування тексту програми. Проведено експерименти із вхідними даними різної структури і обсягів. Результати експери ментів підтвердили, що запропонована методика може бути використана для автоматичної генерації ефе ктивних алгоритмів сортування. А застосування конструктивно-продукційного моделювання у сукупності із генетичним алгоритмом дозволяє ефективно виконувати структурну адаптацію алгоритмів.Problems in programming 2026; 1: 40-50 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-04-23 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/890 PROBLEMS IN PROGRAMMING; No 1 (2026); 40-50 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2026); 40-50 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2026); 40-50 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/890/943 Copyright (c) 2026 PROBLEMS IN PROGRAMMING |
| spellingShingle | constructive-synthesizing modeling sorting algorithm time efficiency genetic algorithm software information technology UDC 004.4 Shynkarenko, V.I. Makarov, O.V. Constructive-synthesizing production of sorting programs adapted by genetic algorithm |
| title | Constructive-synthesizing production of sorting programs adapted by genetic algorithm |
| title_alt | Конструктивно-продукційне формування програм сортування, адаптованих генетичним алгоритмом |
| title_full | Constructive-synthesizing production of sorting programs adapted by genetic algorithm |
| title_fullStr | Constructive-synthesizing production of sorting programs adapted by genetic algorithm |
| title_full_unstemmed | Constructive-synthesizing production of sorting programs adapted by genetic algorithm |
| title_short | Constructive-synthesizing production of sorting programs adapted by genetic algorithm |
| title_sort | constructive-synthesizing production of sorting programs adapted by genetic algorithm |
| topic | constructive-synthesizing modeling sorting algorithm time efficiency genetic algorithm software information technology UDC 004.4 |
| topic_facet | constructive-synthesizing modeling sorting algorithm time efficiency genetic algorithm software information technology UDC 004.4 конструктивно-продукційне моделювання алгоритми сортування часова ефективність генетичний алгоритм програмне забезпечення інформаційні технології УДК004.4 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/890 |
| work_keys_str_mv | AT shynkarenkovi constructivesynthesizingproductionofsortingprogramsadaptedbygeneticalgorithm AT makarovov constructivesynthesizingproductionofsortingprogramsadaptedbygeneticalgorithm AT shynkarenkovi konstruktivnoprodukcíjneformuvannâprogramsortuvannâadaptovanihgenetičnimalgoritmom AT makarovov konstruktivnoprodukcíjneformuvannâprogramsortuvannâadaptovanihgenetičnimalgoritmom |