Essays/Order Statistics
< Essays
Jump to navigation
Jump to search
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
See also
Contributed by Roger Hui.