A Fast and Practical Algorithm for Selection Problems

Title: A Fast and Practical Algorithm for Selection Problems

Abstract: This research article introduces a new algorithm called Select, which is an improved version of an algorithm proposed by Floyd and Rivest in 1975. The algorithm is designed to find the kth smallest element in a set of n elements, with a focus on minimizing the number of comparisons needed. The main contributions of this paper are:

1. A revised version of the Select algorithm that simplifies its analysis. 2. An average-case analysis of the Select algorithm, showing that it requires at most n + min {k, n−k} + O(n^2/3 ln^1/3 n) comparisons, with ln^1/3 n replaced by ln^1/2 n for the original samples of Floyd and Rivest. This result improves upon the previous best bounds for median selection and random rank selection. 3. An implementation strategy for the Select algorithm that uses tripartitioning schemes and random sampling, which leads to better performance than previous implementations.

The computational results suggest that the Select algorithm outperforms other selection methods, such as Hoare's Find or quickselect with median-of-3 pivots, in both comparison counts and computing times. This makes the Select algorithm a practical choice for solving selection problems.

Link to Article: https://arxiv.org/abs/0401003v1 Authors: arXiv ID: 0401003v1