| Home |
| About |
| Submission |
| Updating Entries |
| Using Entries |
| Search |
| Statistics |
| Index |
| Download |
The Median-of-Medians Selection Algorithm
| Title: | The Median-of-Medians Selection Algorithm |
| Author: | Manuel Eberl |
| Submission date: | 2017-12-21 |
| 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. |
| BibTeX: |
@article{Median_Of_Medians_Selection-AFP,
author = {Manuel Eberl},
title = {The Median-of-Medians Selection Algorithm},
journal = {Archive of Formal Proofs},
month = dec,
year = 2017,
note = {\url{http://isa-afp.org/entries/Median_Of_Medians_Selection.html},
Formal proof development},
ISSN = {2150-914x},
}
|
| License: | BSD License |
| Used by: | KD_Tree |
| Status: [ok] | This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations. |
|
Proof outline Proof document |
| Browse theories |
| Download this entry |