Асинхронный алгоритм сортировки массива чисел с использованием ингибиторных сетей Петри

В настоящее время задачи ускорения вычислений и/или их оптимизация является достаточно актуальной задачей. Среди направлений решения вышеприведенной задачи в статье рассматривается применение подхода распараллеливания и асинхронизации алгоритма сортировки. Предлагается метод сортировки, основанный на принципе разбиения всего массива на множество независимых пар чисел и их параллельное и асинхронное сравнение, что отличает предлагаемый алгоритм от традиционных алгоритмов сортировки (таких как быстрая сортировка, сортировка слиянием, вставками и другие). Алгоритм реализован с использованием сетей Петри как наиболее подходящего инструмента для описания асинхронных систем, а также приведен пример его работы. В статье выполнена оценка быстродействия алгоритма для наилучшего и наихудших случаев. В наилучшем случае алгоритм выполняется за 2 или 3 условных такта в зависимости от разбиения массива на пары соседних элементов. В наихудшем случае — за n или за 3n/2, где n — число элементов. Принципы распараллеливания и асинхронизации, использованные при построении алгоритма, также могут быть применены для других алгоритмов.