ДОСІДЖЕННЯ ТА РЕАЛІЗАЦІЯ ПАРАЛЕЛЬНОГО АЛГОРИТМУ СОРТУВАННЯ TIM SORT
Валерій Олександрович Денисюк, Євген Віталійович Томчук
Остання редакція: 2025-11-23
Анотація
Розглянуто розробку паралельного алгоритму сортування на основі TimSort з використанням механізмів багатопоточності C#. Виконано аналіз існуючих методів сортування, обґрунтовано вибір алгоритму TimSort як базового завдяки його гібридній природі та високій ефективності на частково впорядкованих наборах даних. Розроблено програмну реалізацію паралельного варіанта TimSort із використанням бібліотеки Task Parallel Library. Наведено UML-діаграми програмного модуля, описано структуру розробленої системи та обґрунтовано вибір програмного середовища реалізації. Проведено тестування продуктивності розробленого паралельного алгоритму на різних наборах вхідних даних. Отримані результати демонструють покращення швидкодії під час обробки великих масивів та зростання продуктивності при збільшенні кількості потоків, що підтверджує ефективність використання паралельного TimSort в задачах, які потребують інтенсивної обробки даних.
Ключові слова
TimSort, паралельне сортування, C#, TPL, продуктивність
Посилання
1.Source Wikipedia, LLC Books. Sorting Algorithms: Sorting Algorithm, Merge Sort, Radix Sort, Insertion Sort, Heapsort, Selection Sort, Shell Sort, Bucket Sort. Нью-Йорк : General Books LLC, 2010. 238 с.
2.Бхаргава А. Grokking Algorithms: An illustrated guide for programmers and other curious people. Нью-Йорк : Simon and Schuster, 2016. 256 с.
3.Wikipedia. TimSort Algorithm. URL: https://uk.wikipedia.org/wiki/Timsort/.
4.GitHub. TimSort Algorithm in C#. URL: https://gist.github.com/indication/1299013/.
5.GeeksforGeeks. TimSort Algorithm. URL: https://www.geeksforgeeks.org/dsa/timsort/.
6.Kirupa. All About Timsort. URL: https://www.kirupa.com/sorts/timsort.htm.
7.Medium. Tim Sort: Powering Through Real-World Data Sorting. URL: https://medium.com/@serene_mulberry_tiger_125/tim-sort-powering-through-real-world-data-sorting-c4940fd7c363
8.Parallel programming in .NET: A guide to the documentation. URL: https://learn.microsoft.com/uk-ua/dotnet/standard/parallel-programming/.