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.
Reference: http://ndevilla.free.fr/median/median.pdf
After som more googling, I found this text by Wirth himself: http://www.oberon2005.ru/book/ads2004.pdf 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. Sturla Molden