search

scijs / ndarray-select

Quick select algorithm for ndarrays
MIT License
8 stars 0 forks source link

Bad worst case behaviour. #1

Open jaspervdg opened 9 years ago

jaspervdg commented 9 years ago

The worst case behaviour of quick select is well-known to be quadratic. For a general-purpose module it would be better to use introselect for example, so we can guarantee decent (linear) worst case behaviour. (Apparently directly using medians-of-medians or soft heaps is not very competitive, and introselect seems easy enough to implement in principle.)

mikolalysenko commented 9 years ago

Awesome, thanks for the info. Do you have some references? I should really update my knowledge on this subject. Also, do you want to dig into fixing this up or should I just do it?

jaspervdg commented 9 years ago

I think Wikipedia is probably as good a starting point as any. Basically the idea is simply to check that you decrease the problem size by a large enough factor every so many steps, and to switch to picking a good enough approximation to the true median for the pivot if you don't. I created the issue to not forget fixing this at some point, but if you have the time and inclination to fix it, by all means, go ahead.