## Improvement
with approximate ranking
## The new idea
We use an approximate rank for each point chosen by the sorting network. Let
sign(x) = 1 if x>0, 0 if x=0, and –1 if x<0. On
the other hand, if lies inside [ro ## The key structure
Suppose
we have a "reference" point at x=r and we know sign(rank(r)
- t Thus,G A partition of siwe T at r is represented by a permutation p(r,T). p(r,T)
= (p Partition p(r,T) is thus an approximation to pi(r). So we define the approximate rank ro(r,T) to be the number of inversions in p(r,T). Because
p(r,T) represents the partition, it can differ from pi(r) only with respect to inversions between pairs of lines within the
same group.There are at most "T choose 2" such inversions in
a group, there are n/T groups so ro(r,T) differs from rank(k) by less than nT/2. Therefore, for any given
value of T, e Let T such that, |ro(r,T)-k|<=nT and |ro(r,T/2)-k|>nT/2. From
the last condition, we are able to determine the relative position of
r and t Moreover,
these two conditions imply the fact that nT/4<|rank(z)-k|<3nT/2. ## The flow
of control
We
now describe the flow of control in the approximation algorithm. The algorithm
maintain two reference points : r When
the network gives a new query point x=q (weighted median point of n/2
points), if q lies outside [r If
q< t If
q> t But
we do not know the relative ordering of q, an attempt is to modify the
partition at r, the active reference point. The attempt will be aborted
if |rank(r)-rank(q)| is "large"; in this case, the other reference
point becomes active and the partition at this reference point is modified
to give the partition at q. Position
q then replaces the appropriate reference point (on the same side of t We claim that this algorithm has an O(nlogn)-time complexity for any k. (proof by the correctness and the computation of each function, for example, partition, of this algorithm) |