# The complexity of lexicographic sorting and searching

Aplikace matematiky (1981)

- Volume: 26, Issue: 6, page 432-436
- ISSN: 0862-7940

## Access Full Article

top## Abstract

top## How to cite

topWiedermann, Juraj. "The complexity of lexicographic sorting and searching." Aplikace matematiky 26.6 (1981): 432-436. <http://eudml.org/doc/15214>.

@article{Wiedermann1981,

abstract = {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.},

author = {Wiedermann, Juraj},

journal = {Aplikace matematiky},

keywords = {asymptotically optimal sorting algorithm; static data structure; lexicographic search tree; asymptotically optimal sorting algorithm; static data structure; lexicographic search tree},

language = {eng},

number = {6},

pages = {432-436},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {The complexity of lexicographic sorting and searching},

url = {http://eudml.org/doc/15214},

volume = {26},

year = {1981},

}

TY - JOUR

AU - Wiedermann, Juraj

TI - The complexity of lexicographic sorting and searching

JO - Aplikace matematiky

PY - 1981

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 26

IS - 6

SP - 432

EP - 436

AB - 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.

LA - eng

KW - asymptotically optimal sorting algorithm; static data structure; lexicographic search tree; asymptotically optimal sorting algorithm; static data structure; lexicographic search tree

UR - http://eudml.org/doc/15214

ER -

## References

top- M. L. Fredman, 10.1016/0304-3975(76)90078-5, Theoretical Computer Science 1, 1976, pp. 355 - 361. (1976) Zbl0327.68056MR0416100DOI10.1016/0304-3975(76)90078-5
- R. L. Rivest, Partial-match retrieval algorithms, SIAM J. Computing 5, 1976, pp. 115-174. (1976) Zbl0331.68064MR0395398
- J. van Leeuwen, The complexity of data organisation. Foundations of computer science II, Part 1. Mathematical centre tracts 81, Mathematisch centrum, Amsterdam 1976. (1976) MR0560287
- J. Wiedermann, Search trees for associative retrieval, (in Slovak). Informačné systémy 1, 1979, pp. 27-41. (1979)

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.