Quickselect: Difference between revisions
Jump to navigation
Jump to search
mNo edit summary |
mNo edit summary |
||
| Line 1: | Line 1: | ||
{{#addbodyclass:tag_tech}} | |||
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" | ||
Latest revision as of 23:33, 21 April 2024
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"