Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
Source
Material
Years
Keywords
  • 1
    Electronic Resource
    Electronic Resource
    Stable in situ sorting and minimum data movement (1990)
    Springer
    BIT 30 (1990), S. 220-234 
    Details
    ISSN: 1572-9125
    Keywords: E.5 ; F.2.2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02017344
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Stacks, queues, and deques with order-statistic operations (1992)
    Springer
    Acta informatica 29 (1992), S. 395-414 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01193574
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...