SOFTWARE IMPLEMENTATION AND RESEARCH OF QUICK SORTING ALGORITHMS
ПРОГРАМНА РЕАЛІЗАЦІЯ ТА ДОСЛІДЖЕННЯ АЛГОРИТМІВ ПАРАЛЕЛЬНОГО ШВИДКОГО СОРТУВАННЯ
Сторінки: 95-105. Номер: №4, 2023 (323) 
Автори:
ДЕНИСЮК ВАЛЕРІЙ
Вінницький національний технічний університет
ORCID ID: 0000-0003-1057-3518
e-mail: vad64@i.ua
ПОТАПОВА НАДІЯ
Донецький національний університет імені Василя Стуса м.Вінниця
ORCID ID: 0000-0003-4566-4102
e-mail: potapova.nadin@gmail.com
ЗЕЛІНСЬКА ОКСАНА
Донецький національний університет імені Василя Стуса м.Вінниця
ORCID ID: 0000-0002-9069-1428
e-mail: zeloksanavlad@gmail.com
ТАРАСЮК МИКОЛА
Вінницький національний технічний університет
e-mail: tarasyuk.m12@gmail.com
DENYSIUK VALERII
Vinnytsia National Technical University, Vinnytsia, Ukraine
POTAPOVA NADIIA
Vasyl’ Stus Donetsk National University, Vinnytsia, Ukraine
ZELINSKA OKSANA
Vasyl’ Stus Donetsk National University, Vinnytsia, Ukraine
TARASIUK MYKOLA
Vinnytsia National Technical University, Vinnytsia, Ukraine
DOI: https://www.doi.org/10.31891/2307-5732-2023-323-4-95-105
Анотація мовою оригіналу
Робота присвячена програмній реалізації та дослідженню алгоритмів паралельного швидкого сортування. А саме для випадку, коли немає можливості використати надбання технологій OpenMP або CUDA, які орієнтовані на C++. Розроблено оригінальну програму, яка реалізує паралельні алгоритми сортування у вигляді консольного додатку засобами мови С#. Розвиток розподілених систем та паралельних обчислень впливає на розвиток алгоритмів з використанням паралельних технологій. Виникає необхідність порівняння ефективності алгоритмів, що використовують технології розподілених систем та паралельних обчислень. Для програмної реалізації обрано відомі алгоритми паралельного швидкого сортування: послідовне швидке сортування; наївне паралельне сортування; оптимізоване паралельне сортування; паралельно-послідовне сортування; гіпершвидке сортування; паралельне швидке сортування шляхом регулярної вибірки. Надано матеріал по кожному алгоритму мовою C#. Зроблено порівняння швидкодії розглянутих паралельних алгоритмів сортування. Можливість порівняння ефективності алгоритмів є цікавою та пізнавальною в учбовому процесі підготовки ІТ-спеціалістів.
Програмна реалізація дослідження алгоритмів сортування виконується в ітеративному режимі за кілька кроків: завантажити програму; у відкритому консольному вікні ввести бажану довжину масиву сортування; ввести мінімальне значення елемента масиву; ввести максимальне значення елемента масиву: із списку доступних алгоритмів сортування обрати бажаний; після вибору алгоритму сортування відбувається сортування масиву, виводиться час сортування та відсортований масив. У результаті досліджень з’ясовано, що для технологій, пов’язаних з C#, найкращим із розглянутих алгоритмів є гіпершвидке сортування, а прийнятними – оптимізоване паралельне сортування або наївне паралельне сортування.
Ключові слова: програма, алгоритм, сортування, паралельне сортування, паралельні обчислення.
Розширена анотація англійською мовою
The article is devoted to software implementation and research of parallel quick sorting algorithms. Namely for the case when it is not possible to use the assets of OpenMP or CUDA technologies, which are oriented towards C++. An original program has been developed that implements parallel sorting algorithms in the form of a console application using the C#. The development of distributed systems and parallel computing affects the development of algorithms using parallel technologies. There is a need to compare the efficiency of algorithms using technologies of distributed systems and parallel computing. Well-known parallel quick sorting algorithms were selected for software implementation: sequential quick sorting; naive parallel quick sorting; optimized parallel quick sorting; parallel-serial sorting; hyperquick sorting; parallel quicksort by regular sampling. Material on each algorithm in C# is provided. A comparison of the speed of the considered parallel sorting algorithms was made. The possibility of comparing the efficiency of algorithms is interesting and informative in the educational process of training IT specialists. The software implementation of the research of quick sorting algorithms is performed in an iterative mode in a few steps: download the program; in the open console window, enter the desired length of the sorting array for generation; enter the minimum value of the array element; enter the maximum value of the array element: choose the desired one from the list of available sorting algorithms (enter the serial number from the list of algorithms from 1 to 6); after selecting the sorting algorithm, the array is sorted, then the sorting time in milliseconds (ms) is displayed. and a sorted array. As a result of the research, it was found that for technologies related to C#, the best of the considered algorithms is hyperfast sort, and optimized parallel sort or naive parallel sort are acceptable.
Key words: program, algorithm, sorting, parallel sorting, parallel computations
