[Numpy-discussion] A faster median (Wirth's method)
Mon Aug 31 23:50:30 CDT 2009
Sturla Molden skrev:
> We recently has a discussion regarding an optimization of NumPy's median
> to average O(n) complexity. After some searching, I found out there is a
> selection algorithm competitive in speed with Hoare's quick select.
After som more googling, I found this text by Wirth himself:
The method is described on page 61 (57 in the PDF) as Hoare's quick
select. So it seems it's just a less optimized version than that of
Numerical Receipes, and the first reference (Devillard) was confused.
Anyhow, it still has the advantage of looking nice in Cython and being
very different from the Numerical Receipes code. We can rename
wirthselect to quickselect then. Sorry for the confusion. I should have
checked the source better.
More information about the NumPy-Discussion