Особливості представлення мережного алгоритму сортування з ранжуванням

Abstract

The improvement of known sorting algorithms and the development of new approaches to sorting is primarily due to their widespread use in the most common application areas today. This affects, for example, to search engines, DB control systems, neural network and expert technologies, pre-processing of signals and images. Along with developed software tools for sorting data arrays, hardware implementation models of sorting are of some interest, as one of the most widespread associative-logical operations. This especially applies to parallel sorting methods, which include variants of their network representation. The article considers the peculiarities of the network algorithm for sorting a linear numerical array based on the well-known method of pair exchange. A feature of the proposed approach is the use of formed ranks of the array corresponding elements in the process of sorting them. As a result, the gradual transformation (tuning) of the ranks of the array elements allows you to abandon the need to perform a complex procedure of commutation of the elements themselves in the formed pairs. This time-consuming operation is replaced by high-speed increment/decrement operations on the corresponding ranks. For comparison, an example of the cycles of two sorting processes is shown in the form of a table: according to the classic network method of pair exchange and the proposed approach with the formation of the corresponding ranks. A classic version of the step-by-step description of the network sorting algorithm with ranking is presented. For comparison, a description of this algorithm in terms of the system of algorithmic algebras (SAA) Glushkov is presented. This approach shows the compact presentation of the proposed algorithm, and also allows showing a significant level of processing parallelism inherent in network sorting algorithms.

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