Structural Adaptation of Sorting Algorithms Based on Constructive Fragments
| dc.contributor.author | Shynkarenko, Viktor I. | en |
| dc.contributor.author | Makarov, Oleksii | en |
| dc.date.accessioned | 2024-12-05T09:15:41Z | |
| dc.date.available | 2024-12-05T09:15:41Z | |
| dc.date.issued | 2024 | |
| dc.description | V. Shynkarenko: ORCID 0000-0001-8738-7225 | en |
| dc.description.abstract | ENG: Modern information technologies are based on processing large volumes of data. At the same time, the task of developing and applying effective algorithms for data processing, in particular sorting, remains relevant. Constructive-synthesizing modeling was applied to form the sorting algorithm code. The meta-algorithm of program code generation is presented. Parts of existing sorting algorithms and auxiliary utilities are used for generation. A genetic algorithm was used to select the algorithm with the maximum time efficiency under the given conditions of use. The use of a standard genetic algorithm faces a problem caused by a different number of elementary sorting operations, which leads to the use of chromosomes of different lengths. To solve the problem, a representation of the chromosome in the form of a binary tree is proposed. To form an algorithm that is guaranteed to sort the array, all leaf nodes include the final sorting gene at the end of the initial sequence of genes. This gene is decoded by calling the existing sorting algorithm, which is guaranteed to perform the sorting. Mechanisms of coding and decoding of the sorting algorithm from chromosome have been implemented. Linearization is performed for decoding and formation of the appropriate sorting algorithm: formation of a textual representation using a depth-first tree traversal algorithm. The fitness function is defined as the median sorting time of randomly generated sorting arrays (the same arrays for all chromosomes) in some stable environment, taking into account certain features of these arrays. The use of other fitness functions related to the number of calculations, comparisons or permutations is foreseen. The developed software should be applied in adapting sorting algorithms to stable input data streams and usage environments. An experiment was performed to verify the ability of the developed method and the corresponding software to form time-efficient sorting algorithms in different hardware and software environments. In the performed experiments, one component of the hardware and software environment was varied, namely the features of the data to be sorted. | en |
| dc.description.abstract | UKR: Сучасні інформаційні технології базуються на обробці великих обсягів даних. При цьому актуальною залишається задача розробки та застосування ефективних алгоритмів обробки даних, зокрема сортування. Для формування коду алгоритму сортування було застосовано конструктивно-синтезуюче моделювання. Представлено метаалгоритм генерації програмного коду. Для генерації використано частини існуючих алгоритмів сортування та допоміжні утиліти. Для вибору алгоритму з максимальною часовою ефективністю при заданих умовах використання використано генетичний алгоритм. Використання стандартного генетичного алгоритму стикається з проблемою, викликаною різною кількістю елементарних операцій сортування, що призводить до використання хромосом різної довжини. Для вирішення проблеми запропоновано представлення хромосоми у вигляді бінарного дерева. Для формування алгоритму, який гарантовано сортує масив, всі вузли листків включають кінцевий ген сортування в кінці початкової послідовності генів. Цей ген декодується викликом існуючого алгоритму сортування, який гарантовано виконує сортування. Реалізовано механізми кодування та декодування алгоритму сортування з хромосоми. Для декодування та формування відповідного алгоритму сортування виконується лінеаризація: формування текстового представлення за допомогою алгоритму обходу дерева в глибину. Фітнес-функція визначається як медіанний час сортування випадково згенерованих сортувальних масивів (однакових масивів для всіх хромосом) у деякому стабільному середовищі з урахуванням певних особливостей цих масивів. Передбачається використання інших фітнес-функцій, пов'язаних з кількістю обчислень, порівнянь або перестановок. Розроблене програмне забезпечення доцільно застосовувати для адаптації алгоритмів сортування до стабільних вхідних потоків даних та середовищ використання. Проведено експеримент для перевірки здатності розробленого методу та відповідного програмного забезпечення формувати ефективні за часом алгоритми сортування в різних апаратно-програмних середовищах. У проведених експериментах варіювався один компонент програмно-апаратного середовища, а саме особливості даних, що підлягають сортуванню. | uk_UA |
| dc.identifier.citation | Shynkarenko V., Makarov O. Structural Adaptation of Sorting Algorithms Based on Constructive Fragments. CEUR Workshop Proceedings. Vol. 3806 : Proc. of the 14th International Scientific and Practical Programming Conference (UkrPROG 2024), Kyiv, Ukraine, May 14–15, 2024. Kyiv, 2024. P. 16–29. | en |
| dc.identifier.issn | 1613-0073 | |
| dc.identifier.uri | https://ceur-ws.org/Vol-3806/ | en |
| dc.identifier.uri | https://crust.ust.edu.ua/handle/123456789/19276 | en |
| dc.language.iso | en | |
| dc.publisher | CEUR-WS Team, Aachen, Germany | en |
| dc.subject | information technology | en |
| dc.subject | software | en |
| dc.subject | sorting | en |
| dc.subject | constructive-synthesizing modeling | en |
| dc.subject | genetic algorithm | en |
| dc.subject | binary tree | en |
| dc.subject | інформаційні технології | UK_UA |
| dc.subject | програмне забезпечення | UK_UA |
| dc.subject | сортування | UK_UA |
| dc.subject | конструктивно-синтезуюче моделювання | UK_UA |
| dc.subject | генетичний алгоритм | UK_UA |
| dc.subject | бінарне дерево | UK_UA |
| dc.subject | КІТ | UK_UA |
| dc.subject.classification | TECHNOLOGY::Information technology | en |
| dc.title | Structural Adaptation of Sorting Algorithms Based on Constructive Fragments | en |
| dc.title.alternative | Структурна адаптація алгоритмів сортування на основі конструктивних фрагментів | UK_UA |
| dc.type | Article | en |