Geodesic
The complexity of lexicographic sorting and searching
Applications of Mathematics, Tome 26 (1981) no. 6, pp. 432-436
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

An asymptotically optimal sorting algorithm that uses $\Theta (n(log\ n+k))$ component comparisons to lexicographically sort the set of $n$ $k$-tuples is presented. This sorting algorithm builds the static data structure - the so called optimal lexicographic search tree - in which it is possible to perform member searching for an unknown $k$-tuple in at most $[(log_2(n+1)]+k-1$ comparisons. The number of comparisons used by this search algorithm is optimal.
An asymptotically optimal sorting algorithm that uses $\Theta (n(log\ n+k))$ component comparisons to lexicographically sort the set of $n$ $k$-tuples is presented. This sorting algorithm builds the static data structure - the so called optimal lexicographic search tree - in which it is possible to perform member searching for an unknown $k$-tuple in at most $[(log_2(n+1)]+k-1$ comparisons. The number of comparisons used by this search algorithm is optimal.
DOI : 10.21136/AM.1981.103933
Classification : 68C25, 68E05, 68P10
Keywords: asymptotically optimal sorting algorithm; static data structure; lexicographic search tree 
@article{10_21136_AM_1981_103933,
     author = {Wiedermann, Juraj},
     title = {The complexity of lexicographic sorting and searching},
     journal = {Applications of Mathematics},
     pages = {432--436},
     year = {1981},
     volume = {26},
     number = {6},
     doi = {10.21136/AM.1981.103933},
     mrnumber = {0634280},
     zbl = {0467.68057},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1981.103933/}
}
TY  - JOUR
AU  - Wiedermann, Juraj
TI  - The complexity of lexicographic sorting and searching
JO  - Applications of Mathematics
PY  - 1981
SP  - 432
EP  - 436
VL  - 26
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1981.103933/
DO  - 10.21136/AM.1981.103933
LA  - en
ID  - 10_21136_AM_1981_103933
ER  - 
%0 Journal Article
%A Wiedermann, Juraj
%T The complexity of lexicographic sorting and searching
%J Applications of Mathematics
%D 1981
%P 432-436
%V 26
%N 6
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1981.103933/
%R 10.21136/AM.1981.103933
%G en
%F 10_21136_AM_1981_103933
Wiedermann, Juraj. The complexity of lexicographic sorting and searching. Applications of Mathematics, Tome 26 (1981) no. 6, pp. 432-436. doi: 10.21136/AM.1981.103933

[1] M. L. Fredman: How good is the information theory bound in sorting?. Theoretical Computer Science 1, 1976, pp. 355 - 361. | DOI | MR | Zbl

[2] R. L. Rivest: Partial-match retrieval algorithms. SIAM J. Computing 5, 1976, pp. 115-174. | MR | Zbl

[3] J. van Leeuwen: The complexity of data organisation. Foundations of computer science II. Part 1. Mathematical centre tracts 81, Mathematisch centrum, Amsterdam 1976. | MR

[4] J. Wiedermann: Search trees for associative retrieval. (in Slovak). Informačné systémy 1, 1979, pp. 27-41.

Cité par Sources :