Сортування квазіупорядкованих масивів

Анотація

В організації обчислювального процесу при задачного-алгоритмічній методі проектування основний етап при зшивці набору алгоритмів до узагальненої блок схему полягає у виборі часто використовуваного алгоритму, який потім структурно реалізується в операційному автоматі. У класичній побудові комп'ютерних засобів таким загальним алгоритмом є складання, інші алгоритми реалізуються за підтримки цього базового. Математичне забезпечення спільно із операційним (структурним) автоматом складає операційний базис.
У статті розглянуто пропозицію побудови нового операційного базису комп'ютерних засобів для високоточних по обробці комп'ютерних засобів і систем. Високоточна обробка реалізується через разрядно-логарифмічні уявлення. Базовою операцією при яких є сортування масивів, елементами яких є короткі цифрові коди. Сортування виконується для впорядкування масивів. При виконанні операцій при розрядно логарифмическом кодуванні масиви деяким чином (в повному обсязі) впорядковані. Тому постановка задачі обрана саме при таких умовах. Головне рішення задачі пропонується в кілька етапів. Впорядкування масиву по блокам з граничними значеннями, впорядкування всередині блоків і стикування блоків між собою з «перекриттям» граничних елементів блоків. Потім повторення сортування всередині блоків і наступні «перекриття». Сортування закінчується при відсутності невпорядкованих елементів. Моделювання визначає скорочення кроків сортування на один-два порядки в порівнянні з сортуванням методом «бульбашки» на гіпотетичній паралельній структурі. Поліпшення базової операції визначає позитивну швидкодію нового операційного базису в цілому.