The Median-of-Medians Selection Algorithm

Manuel Eberl 🌐

December 21, 2017

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

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.

License

BSD License

Topics

Session Median_Of_Medians_Selection

Used by

Cite

× 
@article{Median_Of_Medians_Selection-AFP,
  author  = {Manuel Eberl},
  title   = {The Median-of-Medians Selection Algorithm},
  journal = {Archive of Formal Proofs},
  month   = {December},
  year    = {2017},
  note    = {\url{https://isa-afp.org/entries/Median_Of_Medians_Selection.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download

Download

× Download latest

Older releases: