Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
We analyze multiple Quickselect (MQS), a variant of Quicksort designed to search for several order statistics simultaneously. We show that, when p is an integer fixed with respect to n, the size of the data set, MQS requires an average of (2Hp + 1)n - 8p ln n + O(1) comparisons to find p order statistics, where Hp is the pth harmonic number.
Year of publication: |
1996
|
---|---|
Authors: | Lent, Janice ; Mahmoud, Hosam M. |
Published in: |
Statistics & Probability Letters. - Elsevier, ISSN 0167-7152. - Vol. 28.1996, 4, p. 299-310
|
Publisher: |
Elsevier |
Keywords: | Sorting Analysis of algorithms Selection of order statistics Random binary search tree |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Estimating an energy consumer price index from establishment survey data
Lent, Janice, (2011)
-
Effects of extreme values on price indexes : the case of the air travel price index
Lent, Janice, (2004)
-
A transaction price index for air travel
Lent, Janice, (2005)
- More ...