Quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and is also known as Hoare's selection algorithm. Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data based on the pivot, but instead of recursing into both sides it only recurses into the side holding the element it is searching for, reducing the average complexity to linear time with a quadratic worst case.
Facts
Time Complexity
Time Complexity (category) Classification
Design Technique Connections
Credited To
Source Quickselect (Wikipedia)
In Field
Source Quickselect (Wikipedia)
Invented By
Source Quickselect (Wikipedia)
Uses Design Technique
Sources
1. Quickselect (Wikipedia)
Wikipedia infobox: time complexity linear
linear
Wikipedia: design technique divide-and-conquer
divide-and-conquer
Credited To: Tony Hoare, Intro, lead sentence
Tony Hoare
In Field: Algorithms and Complexity Theory, Lead sentence
quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic.
Invented By: Tony Hoare, Intro, lead sentence
Tony Hoare
In Group: Selection Algorithms, Lead
In computer science, quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.