Improved randomized selection
Kiwiel, Krzysztof C.
Original · EN
We show that several versions of Floyd and Rivest's improved algorithm Select for finding the kth smallest of n elements require at most n+{k,n-k}+O(n¹/²¹/²n) comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Encouraging computational results on large median-finding problems are reported.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.