Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
asymptotically optimal sorting algorithm; static data structure; lexicographic search tree
asymptotically optimal sorting algorithm; static data structure; lexicographic search tree
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.
References:
[1] M. L. Fredman: How good is the information theory bound in sorting?. Theoretical Computer Science 1, 1976, pp. 355 - 361. DOI 10.1016/0304-3975(76)90078-5 | MR 0416100 | Zbl 0327.68056
[2] R. L. Rivest: Partial-match retrieval algorithms. SIAM J. Computing 5, 1976, pp. 115-174. MR 0395398 | Zbl 0331.68064
[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
[4] J. Wiedermann: Search trees for associative retrieval. (in Slovak). Informačné systémy 1, 1979, pp. 27-41.
Search
Partner of
