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.

For citation:

Artamonov Y.N. Using the Complete Sequences for Sorting Natural Numbers. The Bulletin of Irkutsk State University. Series Mathematics, 2017, vol. 22, pp. 3-17. (In Russian). https://doi.org/10.26516/1997-7670.2017.22.3

MSC

68P10

DOI

https://doi.org/10.26516/1997-7670.2017.22.3

1. Artamonov Y.N. Group choice using matrix norms. Izv. Irkutsk. Gos. Univ. Ser. Mat., 2016, vol. 18, pp. 3-20. (in Russian).

2. Knuth D.E. Iskusstvo programmirovanija, vol. 3. Sortirovka i poisk [The art of computer programming, volume 3. Sorting and searching]. Vil’jams, 2007, pp. 274-387.

3. Cormen T., Leiserson C., Rivest R., Stein C. Algoritmy: postroenie i analiz [Algorithms: construction and analysis.] Vil’jams, 2005, pp. 220-238.

4. Nauchnyj forum dxdy. Modifikacija staroj zadachi pro meshki s monetami (jelektronnyj resurs) [The scientific forum dxdy. Modification of the old problem of bags with coins (electronic resource)] Available at: http://dxdy.ru/topic111132-30.html (accessed 2 November 2017).

5. Nacional’nyj otkrytyj universitet «INTUIT», proekt diofant.ru (jelektronnyj resurs)[National Open University «INTUIT», project diofant.ru (electronic resource)] Available at: http://www.diofant.ru/problem/383/ (accessed 2November 2017).

6. Sedjvik R. Fundamental’nye algoritmy na C++. Analiz. Struktury dannyh. Sortirovka. Poisk [Fundamental algorithms in C++. Analysis. Data structures. Sorting. Search.] DiaSoft, 2001, pp. 401-438.

7. Goodrich M., Michael T., Tamassia, R. 4.5 Bucket-Sort and Radix-Sort. Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley, 2002, pp. 241-243.

8. Honsberger R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., 1985, pp. 123-128.