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

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.