Linear-time in-place selection with \(\varepsilon \cdot n\) element moves. (English) Zbl 1119.68061

Geffert, Viliam; Kollár, Ján

Comput. Inform. 25, No. 4, 333-350 (2006).

Summary: We present a new in-place selection algorithm that finds the \(k^{\text{th}}\) smallest element in an array of \(n\) elements in linear time, using only \(\varepsilon \cdot n\) element moves. Here \(\varepsilon > 0\) denotes an arbitrarily small, but fixed, real constant. As a consequence, partitioning the array in-place into segments of elements with ranks smaller than, equal to, and larger than \(k\) can be performed with \((1 + \varepsilon )\cdot n\) element moves. Minimizing the sum of comparisons and moves, we get a selection algorithm using \(C(n) < 10.236\,n\) comparison and \(M(n)< 0.644\,n\) moves. The algorithm can be further optimized, by tuning up for the given cost ratio between a single move and a single comparison. As an example, we present an algorithm with \(C(n)+ 10\cdot M(n)\leq 13.634\,n\).

MSC:

68P10	Searching and sorting
68W05	Nonnumerical algorithms

Keywords:

algorithms; in-place selection; sorting