ZIB

Treffer pro Seite

Treffer 1 - 2 | 2 Treffer

Sortierung

Digitale Medien

Stable in situ sorting and minimum data movement (1990)

Munro, J. Ian ; Raman, Venkatesh ; Salowe, Jeffrey S.

Springer

BIT 30 (1990), S. 220-234

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1572-9125

Schlagwort(e): E.5 ; F.2.2

Quelle: Springer Online Journal Archives 1860-2000

Thema: Mathematik

Notizen: Abstract In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg(k+1) n+kn) comparisons (lg(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result ≤ 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/BF02017344

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Digitale Medien

Stacks, queues, and deques with order-statistic operations (1992)

Richards, Dana S. ; Salowe, Jeffrey S.

Springer

Acta informatica 29 (1992), S. 395-414

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1432-0525

Quelle: Springer Online Journal Archives 1860-2000

Thema: Informatik

Notizen: Abstract Anorder-statistic deque is a deque that also supports the operationfind(k, D), wherefind(k, D) returns the item inD with rankk. Assumingk is fixed, we show how to implement an order-statistic deque so thatinject(x, D), eject(D), push(x, D), andpop(D) take O(logk) amortized time andfind(k, D) takes worst-case constant time; the time bounds can be made worst case using a technique of Gajewska and Tarjan. We also show our implementations are optimal in the algebraic decision tree model of computation. This deque is applied to three problems: computing order-statistic filters, finding a smallest area convex quadrilateral in the plane, and computing “batched” order statistics.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/BF01193574

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 2 | 2 Treffer