Using the Complete Sequences for Sorting Natural Numbers

Complete sequences are defined as infinite sequences of natural numbers, with the help of which it is possible to represent any other natural number. The most significant result, allowing to judge the completeness of any sequence, was obtained by D. Brown. The article poses the problem of representing the complete sequence of all natural numbers up to a certain limit as a sum of elements (such initial segments of complete sequences are called generating sequences). Then there is the problem of finding generating sequences of minimal length for a given limit N. The article proposes algorithms for generation of generating sequences of minimal length. A class of algorithms for generation of generating sequences containing a given generating sequence of shorter length is proposed, it allows us to introduce regular algorithms of generating complete sequences. The proposed regular algorithms for generating complete sequences are used in the development of the algorithm for sorting natural numbers without comparing them, which is the development of the radix sorting algorithm with interpretation of the bits as elements of a suitable complete sequence. The article demonstrates approaches of adapting the work of this algorithm for sorting a specific sorted sequence.

Abstract licence: CC BY-NC

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.