Abstract

We present a new in-place selection algorithm that finds the k rm th smallest element in an array of n elements in linear time, using only ε.n element moves. Here ε>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+ε).n element moves. Minimizing the sum of comparisons and moves, we get a selection algorithm using C(n)<10.236 n comparisons 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.M(n)leq 13.634n.

Keywords

Cite this article

@article{cai-1529,
  author  = {Viliam Geffert and Ján Kollár},
  title   = {Linear-Time In-Place Selection with ε.N Element Moves},
  journal = {Computing and Informatics},
  volume  = {25},
  number  = {4},
  pages   = {333--350},
  year    = {2006},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2006/4/linear-time-in-place-selection-with-epsilon-dot-n-element-moves/}
}
Download .bib