Quickselect: Difference between revisions
Jump to navigation
Jump to search
(Created page with "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"") |
mNo edit summary |
||
| Line 1: | Line 1: | ||
Quickselect is an algorithm that gets the n-th smallest (or largest) item from an unordered list. | 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, | 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" | 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" | ||
Revision as of 11:33, 8 August 2023
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"