The median of medians is an approximate median selection algorithm, used to supply a good pivot to an exact selection algorithm, most commonly quickselect, which finds the kth smallest element of an unsorted array. It finds an approximate median in linear time, and using that value as the pivot reduces the worst case cost of quickselect from quadratic to linear, which is also the asymptotically optimal worst case for any selection algorithm. It works by recursively choosing good pivot elements so that at least 30 percent of the elements are discarded at each step. The same pivot strategy can be applied inside quicksort to give a worst case of O(n log n). The method was published in 1973 and is often called BFPRT after its authors Blum, Floyd, Pratt, Rivest and Tarjan; the original paper named it PICK and called quickselect FIND. In practice it is usually outperformed by simply choosing random pivots, since computing the pivot adds overhead, but it serves as the fallback in the hybrid introselect algorithm, which guarantees worst case linear performance while keeping good average performance.
Facts
Time Complexity
Time Complexity (category) Connections
Credited To
Source Median of medians (Wikipedia)
Source Median of medians (Wikipedia)
Source Median of medians (Wikipedia)
Source Median of medians (Wikipedia)
In Field
Source Median of medians (Wikipedia)
Invented
Source Median of medians (Wikipedia)
Source Median of medians (Wikipedia)
Source Median of medians (Wikipedia)
Source Median of medians (Wikipedia)
Uses Design Technique
Source Median of medians (Wikipedia)
Sources
1. Median of medians (Wikipedia)
Lead [complexity-category]
guarantees a worst-case runtime of O(n)
Article text
The median of medians algorithm guarantees a worst-case runtime of O(n) by recursively selecting good pivot elements, discarding at least 30% of elements at each step.
In Group: Selection Algorithms, Lead
is an approximate median-selection algorithm that helps building an asymptotically optimal, exact general selection algorithm
In Field: Algorithms and Complexity Theory, Lead [in-field]
In computer science, the median of medians is an approximate median selection algorithm
Credited To: Manuel Blum, Lead, last paragraph
sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan)
Credited To: Robert W. Floyd, Lead, last paragraph
sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan)
Credited To: Ron Rivest, Lead, last paragraph
sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan)
Credited To: Robert Tarjan, Lead, last paragraph
sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan)
Invented: Manuel Blum, Lead, last paragraph
The algorithm was published in 1973 and is sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan).
Invented: Robert W. Floyd, Lead, last paragraph
The algorithm was published in 1973 and is sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan).
Invented: Ron Rivest, Lead, last paragraph
The algorithm was published in 1973 and is sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan).
Invented: Robert Tarjan, Lead, last paragraph
The algorithm was published in 1973 and is sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan).
Uses Design Technique: Divide and Conquer, Algorithm, pivot subroutine
divides its input (a list of length n) into groups of at most five elements, computes the median of each of those groups using some subroutine, then recursively computes the true median
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.