ОСОБЛИВОСТІ ПРЕДСТАВЛЕННЯ МЕРЕЖНОГО АЛГОРИТМУ СОРТУВАННЯ З РАНЖУВАННЯМ

Анотація

Вдосконалення відомих алгоритмів сортування та розроблення нових підходів до сортування пов’язано, в першу чергу, з їх широким застосуванням у найпоширеніших у теперішній час прикладних областях. Це стосується, наприклад, пошукових систем, систем управління БД, нейромережних та експертних технологій, попереднього оброблення сигналів і зображень. Поряд з розвинутими програмними засобами сортування масивів даних певний інтерес представляють апаратні реалізаційні моделі сортування, як однієї з найбільш розповсюджених асоціативно-логічних операцій. Особливо це стосується паралельних методів сортування, до яких належать варіанти їх мережного подання. У статті розглянуто особливості мережного алгоритму сортування лінійного числового масиву на базі відомого методу попарного обміну.  Особливістю запропонованого підходу є використання сформованих рангів відповідних елементів масиву в процесі їх сортування. В результаті поступове перетворення (підлаштування) рангів елементів масиву дозволяє відмовитись від необхідності виконання складної процедури перекомутації самих елементів у сформованих парах. Ця трудомістка операція замінюється швидкісними операціями інкремента/декремента над відповідними рангами. Для порівняння у вигляді таблиці показано приклад по циклах двох процесів сортування: за класичним мережним методом попарного обміну і запропонованим підходом з формуванням відповідних рангів. Наведено класичний варіант покрокового опису алгоритму мережного сортування з ранжуванням. Для порівняння представлено опис цього алгоритму у термінах системи алгоритмічних алгебр (САА) Глушкова. Такий підхід свідчить про компактність подання запропонованого алгоритму, а також дозволяє показати значний рівень паралелізму оброблення, притаманний мережним алгоритмам сортування.