Linear-Time In-Place Selection with epsilon.n Element Moves

Authors

  • Viliam Geffert
  • Ján Kollár

Keywords:

Algorithms, in-place selection, sorting

Abstract

We present a new in-place selection algorithm that finds the k-th smallest element in an array of n elements in linear time, using only epsilon.n element moves. Here epsilon>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+epsilon).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)<= 13.634n.

Downloads

Download data is not yet available.

Downloads

Published

2012-01-30

How to Cite

Geffert, V., & Kollár, J. (2012). Linear-Time In-Place Selection with epsilon.n Element Moves. Computing and Informatics, 25(4), 333–350. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/345