Classification Analysis of Sorting Methods

Abstract

The basic procedure in many search systems is associative processing, namely the processes of sorting, ranking, and selection by key. These processes are important due to the need to speed up the work of the corresponding algorithms, where certain elements of the data array need to be frequently accessed. The need for parallel methods and tools for associative processing of large data sets is also related to the area of their effective application, for example, in relational databases, knowledge bases, expert systems, and the analysis of semantic networks. In this article, the analysis of the functional and implementation possibilities of the sorting process by known and alternative methods, taking into account time dependencies, was carried out. The applied aspect of the application of sorting and ranking operations in such areas as median filtering during pre-processing of signals and images, neural network classification of objects, and decision support subsystem in expert systems is considered. A classification model of one-dimensional array sorting methods is proposed, which are divided into two groups according to such a feature as the use of the pairwise comparison operation and the permutation of the elements of the numerical array. The first group consists of classic sorting methods, and the second group contains alternative sorting methods with slice processing. In the table, the characteristics of the sorting methods of the first group are considered according to such characteristics as the total number of comparisons and the average number of moves, which correlate with the time and hardware costs of their implementation, respectively. The functional structure of vertically-parallel processing of a one-dimensional array of numbers using decrement and increment operations is given as an example of the sorting method of the second group. At the same time, it is shown that the use of high-speed operations of increment and decrement as a result makes it possible to determine the maximum, minimum, and average element of the array by size. A comparison of the given time dependences of the two groups of algorithms shows that the sorting methods of the second group have a higher speed or a speed that does not depend on the number of elements of the array being sorted. At the same time, the hardware implementation of the sorting methods of both groups is in most cases implemented on devices with a sufficient level of regularity of the structure, but with different degrees of hardware costs.