КЛАСИФІКАЦІЙНИЙ АНАЛІЗ МЕТОДІВ СОРТУВАННЯ

Анотація

Основною процедурою у багатьох пошукових системах є асоціативне оброблення, а саме процеси сортування, ранжування та вибірки за ключем. Ці процеси є важливими через необхідність прискорення роботи відповідних алгоритмів, де потрібно часто звертатися до певних елементів масиву даних. Потреба у паралельних методах та засобах асоціативного оброблення значних масивів даних пов’язана також з областю їхнього ефективного застосування, наприклад, у реляційних базах даних, базах знань, експертних системах, у разі аналізу семантичних мереж.

У роботі проаналізовано функціональні та реалізаційні можливості процесу сортування за відомими та альтернативними методами з урахуванням часових залежностей. Розглянуто прикладний аспект застосування операцій сортування і ранжування в таких областях як: медіанна фільтрація з попереднім обробленням сигналів і зображень, нейромережна класифікація об’єктів, підсистема підтримки прийняття рішень в експертних системах. Запропоновано класифікаційну модель методів сортування одновимірного масиву, які поділяються на дві групи за такими ознаками: застосування операції попарного порівняння та перекомутація елементів числового масиву. Першу групу складають класичні методи сортування, а друга група містить альтернативні методи сортування з позрізовим обробленням. У таблиці характеристики методів сортування першої групи розглянуто за такими ознаками, як загальна кількість порівнянь і середня кількість переміщень, які корелюють відповідно з часовими та апаратними витратами на їхню реалізацію. Наведено функціональну структуру вертикально-паралельного оброблення одновимірного масиву чисел з використанням операцій декремента і інкремента як приклад методу сортування другої групи. Водночас показано, що використання швидкісних операцій інкремента і декремента в результаті дає можливість визначити максимальний, мінімальний і середній елемент масиву за величиною. Порівняння наведених часових залежностей двох груп алгоритмів свідчить про те, що методи сортування другої групи мають більшу швидкодію або швидкодію, що не залежить від кількості елементів масиву, що сортується. При цьому, апаратна реалізація методів сортування обох груп у більшості випадків реалізується на засобах з достатнім рівнем регулярності структури, але з різним ступенем апаратних витрат.