COMPUTATIONAL COMPLEXITY OF THE NETWORK MODEL OF SORTING OF A LINEAR NUMBER ARRAY

Abstract

In the development of advanced software and hardware for modern computing, the interest is the improvement of methods of associative processing of information such as procedures of sorting and selection. That ensures the realization of effective search for the required information in the data arrays. The need for parallel non-processing of large amounts of information entails the appropriate organization of associative memory, as well as the development and using of perspective technical devices. The sorting is important procedure in such application areas as solving economic problems, managing databases, sorting of IP addresses in computer networks, processing signals and images (for example, in nonlinear median image filtering). The analysis of known sorting methods have shown that the most effective method of parallel sorting, taking into account its hardware implementation by the sorting network, is the pairwise exchange. At the same time, the degree of parallelism of any sorting method for its hardware implementation directly depends on the number of comparison schemes that work in parallel in each view. For a pairwise exchange method, the degree of parallelism is determined by the value ]n/2[, where n is the number of input numerical values ​​or the dimension of the input linear number array. In this article methods of implementing of the sorting algorithm by the method of pairwise exchange with the link topology between elements of the number array in the form of "tape" and "ring" are analyzed. For example, the parallel sorting algorithm using the pairwise exchange method is described. The simulation at a high-level C ++ language is done. The obtained statistical and graphic results of modeling are analyzed. The analysis of graphical modeling results shows the dependence of the form O(n) between the number of sort cycles and the dimensionality n of the input array. That confirms the effectiveness of the hardware implementation of sorting by pairwise exchange on the sorting network due to the regularity of the structure and connections in the sorting process. The ability to statistically determine not only the number of sorting cycles with a given dimension of 

the number array, but also the corresponding number of comparisons and transposition greatly extends the possibilities of improving the known and creating new ways of synchronous sorting of elements of a linear array by hardware in the form of a sorting network.