Реалізація паралельного алгоритму сортування Insertion Sort

Abstract

У роботі досліджено алгоритми сортування та можливості їх паралельної реалізації з використанням технології OpenMP. Проведено теоретичний аналіз класичних алгоритмів сортування, зокрема методу вставки (Insertion Sort), а також принципів паралельних обчислень у моделях спільної пам’яті. Описано особливості алгоритму Insertion Sort, його складність, поведінку на різних типах вхідних даних та причини обмежених можливостей прямої паралелізації. На основі проведеного аналізу реалізовано послідовну та паралельну модифікації алгоритму Insertion Sort. Паралельна версія ґрунтується на блочному розбитті масиву та подальшій незалежній обробці підмасивів із використанням директив OpenMP. У ході експериментальної частини виконано тестування коректності сортування та проведено вимірювання продуктивності при різній кількості потоків. Результати показали, що паралельна обробка забезпечує прискорення під час роботи з великими масивами, проте ефективність паралельного алгоритму суттєво залежить від структури вхідних даних та способу розбиття масиву. Отримані дані підтверджують можливість прискорення класичного алгоритму Insert Sort за рахунок паралельної обробки блоків, а також демонструють обмеження та потенційні напрями оптимізації паралельних алгоритмів сортування.

The work investigates sorting algorithms and the possibilities of their parallel implementation using OpenMP technology. A theoretical analysis of classical sorting algorithms, in particular the Insertion Sort method, as well as the principles of parallel computing in shared memory models, is carried out. The features of the Insertion Sort algorithm, its complexity, behavior on different types of input data and the reasons for the limited possibilities of direct parallelization are described. Based on the analysis, a sequential and parallel modification of the Insertion Sort algorithm is implemented. The parallel version is based on block partitioning of the array and subsequent independent processing of subarrays using OpenMP directives. During the experimental part, sorting correctness testing was performed and performance measurements were carried out with different numbers of threads. The results showed that parallel processing provides acceleration when working with large arrays, but the efficiency of the parallel algorithm significantly depends on the structure of the input data and the method of partitioning the array. The obtained data confirm the possibility of accelerating the classical Insert Sort algorithm by parallel processing of blocks, and also demonstrate the limitations and potential directions for optimizing parallel sorting algorithms.