Hacker Newsnew | comments | show | ask | jobs | submit login

You can use a randomized selection algorithm to find the median in linear time, and if you use the median as a pivot you will never get worst case n^2 behavior.

This is not used in practice because the probability of getting worst case behavior is extremely slim if you do some clever, and cheap, tricks.




Randomized selection algoritm is actually O(N^2) in the worst case. Median of medians is the O(N) worst case selection algorithm.

-----




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: