Review of the Parallel Hyperquick Sort Algorithm by C#

Abstract

Sorting is used to arrange large arrays of data and present them in a certain structured form. With the development of distributed systems and parallel computing, algorithms were also developed that used the advantages of these technologies to improve and increase the efficiency of the tasks of sorting data arrays. The article discusses the algorithm for parallel hyperquick sorting of data arrays by C programming language. Hyperquicksort is a type of quicksort algorithm that uses multiple nested items to divide a list into sublists. This allows the algorithm to sort the list faster than the standard quicksort algorithm, The algorithm uses multiple nested elements to divide the list into more than two sublists, which allows the list to be sorted more efficiently, especially when the list is already partially sorted or when it has other special properties. Using multiple aggregates can allow the algorithm to skip large sections of the list that are already in the correct order, instead of recursively sorting them. In the case the list has some other special property, such as a large number of elements that are equal to the reference part, using multiple reference elements can allow the algorithm to partition the list more efficiently. The algorithm is an improvement using a simple combination of serial and parallel approaches. Reduces the problem of load balancing. Improves finding the median by sequentially sorting the sublists using a single reference point that is broadcast to all processes at the beginning of the algorithm. The flow graph and program code of the parallel hyperquick sorting algorithm were developed by C language. The algorithm was tested for a large array of data. To test the parallel hyperquick sort algorithm, a program was created that implements the parallel hyperquick sort algorithm and related algorithms, namely: sequential quick sort; naive parallel sorting; optimized parallel sorting; parallel-serial sorting; parallel quicksort by regular sampling. The testing program has the following capabilities: generation of an array with random values according to the size specified by the user; sorting a randomly generated array of data using one of the ed algorithms; measuring the time spent on sorting an array of N elements. The analysis of the obtained data confirms the good time performance of the proposed algorithm for parallel hyperquick sorting of data arrays in comparison with existing sorting algorithms.

Для впорядкування великих масивів даних та подання їх в певному структурованому вигляді використовується сортування. З розвитком розподілених систем та паралельних обчислень розвивалися і алгоритми, які використовували переваги даних технологій для вдосконалення і підвищення ефективності задач сортування масивів даних.У статті розглянуто алгоритм паралельного гіпершвидкого сортування масивів даних мовою програмування C. Гіпершвидке сортування є різновидом алгоритму швидкого сортування, який використовує кілька зведених елементів для поділу списку на підсписки. Це дозволяє алгоритму сортувати список швидше, ніж стандартний алгоритм швидкого сортування, Алгоритм використовує кілька зведених елементів для поділу списку на більше ніж два підсписки, що дозволяє сортувати список ефективніше, особливо коли список вже частково відсортовано або коли він має інші спеціальні властивості. Використання кількох зведених елементів може дозволити алгоритму пропускати великі розділи списку, які вже знаходяться в правильному порядку, замість того, щоб їх рекурсивно сортувати. У випадку, коли список має деякі інші особливі властивості, наприклад, велика кількість елементів, які дорівнюють опорній частині, використання кількох опорних елементів може дозволити алгоритму розділити список більш ефективно. Алгоритм є вдосконаленням використання простої комбінації послідовного та паралельного підходів. Зменшує проблему балансування навантаження. Покращує знаходження медіани шляхом послідовного сортування підсписків за допомогою однієї опорної точки, яка транслюється усім процесам на початку алгоритму. Розроблено потоковий граф і програмний код алгоритму паралельного гіпершвидкого сортування мовою прогумування C. Проведено тестування алгоритму для великого масиву даних. Для тестування алгоритму паралельного гіпершвидкого сортування створено програму, яка реалізує паралельний алгоритм гіпершвидкого сортування та споріднені алгоритми, а саме: послідовне швидке сортування; наївне паралельне сортування; оптимізоване паралельне сортування; паралельно-послідовне сортування; паралельне швидке сортування шляхом регулярної вибірки. Програма тестування має такі можливості: генерування масиву з випадковими значеннями за розміром заданим користувачем; сортування випадково згенерованого масиву даних за допомогою одного із обраних алгоритмів; вимірювання часу витраченого на сортування масиву з N елементів. Аналіз отриманих даних підтверджує хороші часові показники запропонованого алгоритма паралельного гіпершвидкого сортування масивів даних у порівнянні з існуючимими алгоритмами сортування.