Previous |  Up |  Next


Title: The complexity of lexicographic sorting and searching (English)
Author: Wiedermann, Juraj
Language: English
Journal: Aplikace matematiky
ISSN: 0373-6725
Volume: 26
Issue: 6
Year: 1981
Pages: 432-436
Summary lang: English
Summary lang: Slovak
Category: math
Summary: 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. (English)
Keyword: asymptotically optimal sorting algorithm
Keyword: static data structure
Keyword: lexicographic search tree
MSC: 68C25
MSC: 68E05
MSC: 68P10
idZBL: Zbl 0467.68057
idMR: MR0634280
DOI: 10.21136/AM.1981.103933
Date available: 2008-05-20T18:17:55Z
Last updated: 2020-07-28
Stable URL:
Reference: [1] M. L. Fredman: How good is the information theory bound in sorting?.Theoretical Computer Science 1, 1976, pp. 355 - 361. Zbl 0327.68056, MR 0416100, 10.1016/0304-3975(76)90078-5
Reference: [2] R. L. Rivest: Partial-match retrieval algorithms.SIAM J. Computing 5, 1976, pp. 115-174. Zbl 0331.68064, MR 0395398
Reference: [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 0560287
Reference: [4] J. Wiedermann: Search trees for associative retrieval.(in Slovak). Informačné systémy 1, 1979, pp. 27-41.


Files Size Format View
AplMat_26-1981-6_5.pdf 785.7Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo