Essays/Order Statistics

An expected linear time algorithm for the order statistic x{/:~y (also x{/:y ) is presented here. It is based on the Quicksort strategy of partitioning the argument list into sublists of items less than a randomly chosen "pivot", equal to the pivot, and greater than the pivot. From Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, Section 3.7.

select=: 4 : 0  NB. x{/:~y
 x=. x+(0>x)*#y
 while. 1 do.
  if. 200>#y do. x{/:~y return. end.
  p=. y{~?#y  NB. pivot
  m=. #s=. y#~p>!.0 y
  if. x<m do. y=.s continue. end.
  m=. m++/p=!.0 y
  if. x<m do. p return. end.
  x=. x-m
  y=. y#~p<!.0 y
 end. 
)

selecti=: ] i.!.0 select  NB. x{/:y

For example:

   y=: 1e6 ?@$ 2e9
   x=: ?#y
   
   x select y
100187838
   x{/:~y
100187838

   6!:2 'x select y'
0.0315822
   6!:2 'x{/:~y'
0.551227
   
   x selecti y
130259
   x{/:y
130259

   6!:2 'x selecti y'
0.0441545
   6!:2 'x{/:y'
0.788708

Essays/Order Statistics

See also