| 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:
|
http://hdl.handle.net/10338.dmlcz/103933 |
| . |
| 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. |
| . |
