Data structures and algorithms problems in C++ using STL

Re:Data structures and algorithms problems in C++ using STL by username223 on Friday March 10, 2017 @10:59AM (#13839543)

See "median of medians algorithm": https://en.wikipedia.org/wiki/Median_of_medians

It's hairier than a partial quicksort, but (if you erase the proof and weigh the chalk dust) guaranteed linear time.

[ Parent | on HN ]

Re:Data structures and algorithms problems in C++ using STL by gpderetta on Friday March 10, 2017 @12:13PM (#13840113)

and median of medians can be used to implement quicksort with O(NlogN) worst case. It is usually not worth it as other hybrid quicksorts like introsort are faster in practice.

On an unrelated note, I was once asked to prove the upper bound for median of median on an interview...

[ Parent | on HN ]