✦ LIBER ✦

Introspective sorting and selection revisited

✍ Scribed by John D. Valois

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 221 KB
Volume: 30
Category: Article
ISSN: 0038-0644
DOI: 10.1002/(sici)1097-024x(200005)30:6<617::aid-spe311>3.0.co;2-a

No coin nor oath required. For personal study only.

✦ Synopsis

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 order to reduce the performance penalty for false positives. We present experimental results showing that these techniques provide significant improvements in the running time for worst-case and other troublesome inputs, without sacrificing performance on well-behaved inputs.

📜 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

Selection and sorting with limited stora

Selection and sorting with limited storage

✍ J.I. Munro; M.S. Paterson 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 971 KB

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

Upper bounds for time-space trade-offs i

Upper bounds for time-space trade-offs in sorting and selection

✍ Greg N. Frederickson 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 561 KB

Selection from read-only memory and sort

Selection from read-only memory and sorting with minimum data movement

✍ J.Ian Munro; Venkatesh Raman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 896 KB

Phenylthiocarbamide taste sensitivity re

Phenylthiocarbamide taste sensitivity revisited: Complete sorting test supports residual family resemblance

✍ B. M. Reddy; Dr. D. C. Rao; Jean W. MacCluer 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 537 KB

Phenylthiocarbamide (PTC) taste thresholds were determined in 100 nuclear families using the complete sorting test. Segregation analysis using the mixed model suggested that the variability in PTC thresholds is controlled by a major locus with incomplete dominance as well as by a multifactorial comp