Geodesic
Using the complete sequences for sorting natural numbers
The Bulletin of Irkutsk State University. Series Mathematics, Tome 22 (2017), pp. 3-17 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: complete sequences, sorting algorithms for linear time, non-traditional number systems, algorithms for searching and storing of numerical data.
Mots-clés : radix sort 
@article{IIGUM_2017_22_a0,
     author = {Y. N. Artamonov},
     title = {Using the complete sequences for sorting natural numbers},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {3--17},
     year = {2017},
     volume = {22},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a0/}
}
TY  - JOUR
AU  - Y. N. Artamonov
TI  - Using the complete sequences for sorting natural numbers
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2017
SP  - 3
EP  - 17
VL  - 22
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a0/
LA  - ru
ID  - IIGUM_2017_22_a0
ER  - 
%0 Journal Article
%A Y. N. Artamonov
%T Using the complete sequences for sorting natural numbers
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2017
%P 3-17
%V 22
%U http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a0/
%G ru
%F IIGUM_2017_22_a0
Y. N. Artamonov. Using the complete sequences for sorting natural numbers. The Bulletin of Irkutsk State University. Series Mathematics, Tome 22 (2017), pp. 3-17. http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a0/

[1] Artamonov Y. N., “Group choice using matrix norms”, Izv. Irkutsk. Gos. Univ. Ser. Mat., 18 (2016), 3–20 (in Russian)

[2] Knuth D. E., The art of computer programming, v. 3, Sorting and searching, Vil'jams, 2007, 274–387

[3] Cormen T., Leiserson C., Rivest R., Stein C., Algorithms: construction and analysis, Vil'jams, 2005, 220–238

[4] Modification of the old problem of bags with coins, The scientific forum dxdy (accessed 2 November 2017)

[5] National Open University « INTUIT », project diofant.ru (accessed 2 November 2017)

[6] Sedjvik R., Fundamental algorithms in C++. Analysis. Data structures. Sorting. Search, DiaSoft, 2001, 401–438

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

[8] R. Honsberger, Mathematical Gems III, Math. Assoc. Amer., Washington, DC, 1985, 123–128 | MR