Класифікаційний аналіз методів сортування

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 thecorresponding algorithms, where certain elements of the data array need to be frequently accessed. The need for parallel methods and tools for asso ciative 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 ofvertically-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.