Sökning: id:"swepub:oai:DiVA.org:ltu-8694" >
Sublinear merging a...
Sublinear merging and natural mergesort
-
- Carlsson, Svante (författare)
- Luleå tekniska universitet,Signaler och system
-
- Levcopoulos, Christos (författare)
- Department of Computer Science, Lund University
-
- Petersson, Ola (författare)
- Department of Computer Science, Lund University
-
(creator_code:org_t)
- 1993
- 1993
- Engelska.
-
Ingår i: Algorithmica. - 0178-4617 .- 1432-0541. ; 9:6, s. 629-648
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- The complexity of merging two sorted sequences into one is linear in the worst case as well as in the average case. There are, however, instances for which a sublinear number of comparisons is sufficient. We consider the problem of measuring and exploiting such instance easiness. The merging algorithm presented, Adaptmerge, is shown to adapt optimally to different kinds of measures of instance easiness. In the sorting problem the concept of instance easiness has received a lot of attention, and it is interpreted by a measure of presortedness. We apply Adaptmerge in the already adaptive sorting algorithm Natural Mergesort. The resulting algorithm, Adaptive Mergesort, optimally adapts to several, known and new, measures of presortedness. We also prove some interesting results concerning the relation between measures of presortedness proposed in the literature
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Dependable Communication and Computation Systems
- Kommunikations- och beräkningssystem
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas