# zbMATH — the first resource for mathematics

Linear-time in-place selection with $$\varepsilon \cdot n$$ element moves. (English) Zbl 1119.68061
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