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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.