𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Selection and sorting with limited storage

✍ Scribed by J.I. Munro; M.S. Paterson

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
971 KB
Volume
12
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Introspective Sorting and Selection Algo
Introspective Sorting and Selection Algorithms
✍ DAVID R. MUSSER πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 93 KB

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Θ(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Θ(N 2 . Previous attem

Introspective sorting and selection revi
Introspective sorting and selection revisited
✍ John D. Valois πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 221 KB

We describe two improvements to introspective sorting and selection algorithms: a simple rule for finegrained introspection that detects potential worst-case performance after only a small constant number of partitioning steps, and the use of remedial randomization as an intervention strategy in ord

Selection by pairwise comparisons with l
Selection by pairwise comparisons with limited resources
✍ Paolo Laureti; Joachim Mathiesen; Yi-Cheng Zhang πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 232 KB

We analyze di erent methods of sorting and selecting a set of objects by their intrinsic value, via pairwise comparisons whose outcome is uncertain. After discussing the limits of repeated Round Robins, two new methods are presented: The ran-ΓΏl requires no previous knowledge on the set under conside

Selection, Routing, and Sorting on the S
Selection, Routing, and Sorting on the Star Graph
✍ Sanguthevar Rajasekaran; David S.L. Wei πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 270 KB

We consider the problems of selection, routing, and sorting on an n-star graph (with n! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraph (which we call a "(k, 1, k) chain network") of the star graph which enables us to desi