Остання редакція: 2026-01-25
Анотація
У роботі розглянуто розробку гібридного алгоритму сортування за розрядами (Radix Sort), у якому обчислення часткових операцій виконуються на графічному процесорі (GPU) засобами DirectCompute, а завершальний стабільний етап формування відсортованого масиву виконується центральним процесором (CPU). Проаналізовано існуючі сортувальні алгоритми, визначено їх переваги й недоліки у контексті паралельних обчислень, обґрунтовано вибір Radix Sort як базового методу через його природну декомпозицію на незалежні підзадачі. Розроблено структуру програмного модуля, створено класи і програмну логіку взаємодії CPU–GPU, побудовано програмну реалізацію на основі DirectCompute та проведено тестування продуктивності на різних обсягах вхідних даних. Показано, що гібридний підхід забезпечує коректність сортування й здатний покращувати продуктивність для великих масивів, водночас демонструючи характерні ефекти амортизації накладних витрат при зростанні розміру масиву.
Ключові слова
Посилання
1.Про алгоритми сортування. URL: https://foxminded.ua/alhorytmy -sortuvannia/
2.Selection sort. URL: https://en.wikipedia.org/wiki/Selection_sort
3.Quicksort: історія виникнення та розвитку “найшвидшого” алгоритму сортування. URL: https://phm.cuspu.edu.ua/nauka/naukovopopuliarni-publikatsii/824-quicksort-istoriia-vynyknennia-ta-rozvytkunaishvydshoho- alhorytmu-sortuvannia.html
4.Сортування злиттям: алгоритм, переваги і особливості. URL: https://kafedra.com.ua/sortuvannya -zlyttyam-algorytm-perevagy -i -osoblyvosti/
5.Radix Sort. URL: https://www.ritambhara.in/radix -sort/
6.Паралельні алгоритми та їх складність. URL: https://javarush.com/ua/quests/lectures/ua.javarush.python.core.lecture.level20.lecture05
7.Жуков І.А. Паралельні та розподілені обчислення. Лабораторний практикум / І.А. Жуков, О.В. Корочкін. К. : Корнейчук, 2008. 224 с.
8.Проектування та аналіз обчислювальних алгоритмів: Вступ до алгоритмів [Електронний ресурс]: навчальний посібник для студ. спеціальності 122 «Комп’ютерні науки» / І. В. Федорін; КПІ ім. Ігоря Сікорського. Електронні текстові дані (1 файл: 1,97 Мбайт). Київ: КПІ ім. Ігоря Сікорського, 2022. 115 с.
9.Методичні вказівки до лабораторних робіт з навчальної дисципліни «Паралельні та розподілені обчислення» (частина 1) для здобувачів вищої освіти першого (бакалаврського) рівня за освітньопрофесійною програмою «Комп’ютерна інженерія» спеціальності 123 «Комп’ютерна інженерія» денної і заочної форм навчання [Електронне видання] / Бойчура М. В., Шатний С. В., Шатна А. В. Рівне : НУВГП, 2023. 49 с.
10.C++. Довідкова документація. URL: https://w3schoolsua.github.io/cpp/cpp _ref _reference.html#gsc.tab =0