Linear-Time In-Place Selection with epsilon.n Element Moves
Viliam Geffert ; Ján Kollár
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  Algorithms; in-place selection; sorting
@article{cai345,
     author = {Viliam Geffert and J\'an Koll\'ar},
     title = {Linear-Time In-Place Selection with epsilon.n Element Moves},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai345}
}
Viliam Geffert; Ján Kollár. Linear-Time In-Place Selection with epsilon.n Element Moves. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai345/