Quickselect
Jump to navigation
Jump to search
Quickselect is an algorithm that gets the n-th smallest (or largest) item from an unordered list.
It's named for its relation to quicksort - and in fact works much like it, and has the same time complexity, but only recurses into half as many decisions, which is in specific cases can be a lot faster than "just sort everything an pick by index"