Median-of-Medians (Q41252)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Median_Of_Medians_Selection
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Median-of-Medians |
AFP entry Median_Of_Medians_Selection |
Statements
Manuel Eberl
0 references
This entry provides an executable functional implementation of the Median-of-Medians algorithm for selecting the k -th smallest element of an unsorted list deterministically in linear time. The size bounds for the recursive call that lead to the linear upper bound on the run-time of the algorithm are also proven.
0 references
21 December 2017
0 references
The Median-of-Medians Selection Algorithm (English)
0 references
