A variant of the classical selection problem, called the
*positioning problem*, is considered. In this problem we are given a
sequence *A*[1∶*n*] of size *n*, an integer *k*, 1 ≤ *k* ≤ *n*,
and an ordering function ◯< , and the task is to rearrange the
elements of the sequence such that *A*[*k*] ◯< *A*[*j*] is false
for all *j*, 1 ≤ *j* < *k*, and *A*[ℓ] ◯< *A*[*k*] is false for all
ℓ, *k* < ℓ ≤ *n*.
We present a Las-Vegas algorithm which
carries out this rearrangement efficiently using only a constant amount of
additional space even if the input contains equal elements and
if only pairwise
element comparisons are permitted. To be more precise, the algorithm
solves the positioning problem in-place in linear time using at most
*n* + *k* + *o*(*n*) element comparisons, *k* + *o*(*n*) element exchanges, and
the probability for succeeding within stated time bounds is at least
1−*e*^{−nΩ(1)}. |