Sorting the quasi ordered array

Abstract

In organizing a computational process with a task-algorithmic design method, the main step in stitching a set of algorithms into a generalized block scheme is to select a frequently used algorithm, which is then structurally implemented in an operational machine. In the classical construction of computer tools, such a general algorithm is addition, other algorithms are implemented with the support of this basic one. The software together with the operational (structural) machine makes up the operational basis.

The article considers the proposal to build a new operational basis of computer tools for high-precision processing of computer tools and systems. High-precision processing is implemented through the bit-logarithmic representation. The basic operation in which is the sorting of arrays whose elements are short digital codes. Sorting is done to arrange arrays. When performing operations in bitwise logarithmic coding, arrays are in some way (not completely) ordered. Therefore, the statement of the problem is chosen precisely under such conditions. The main solution to the problem is proposed in several stages. Array ordering by blocks with boundary values, ordering inside blocks and docking blocks with each other with "overlapping" boundary elements of blocks. Then repeat the sorting within the blocks and the subsequent “overlap”. Sorting ends when there are no unordered items. Modeling determines the reduction of sorting steps by one or two orders of magnitude compared to sorting by the "bubble" method on a hypothetical parallel structure. Improving the basic operation determines the positive performance of the new operational basis as a whole.