Fast Deterministic Selection

Andrei Alexandrescu, Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, Rajeev Raman · 2017
PDF · DOI: 10.4230/LIPIcs.SEA.2017.24 · arXiv:1606.00484

Awesomely fast order statistic estimator (guaranteed linear time).

Reference

Andrei Alexandrescu, Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, Rajeev Raman “Fast Deterministic Selection” (2017) DOI: 10.4230/LIPIcs.SEA.2017.24 arXiv:1606.00484

@Inproceedings{alexandrescu2017,
  author = {Andrei Alexandrescu},
  title = {Fast Deterministic Selection},
  booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages = {24:1--24:19},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-036-1},
  issn = {1868-8969},
  year = {2017},
  volume = {75},
  editor = {Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address = {Dagstuhl, Germany},
  url = {http://drops.dagstuhl.de/opus/volltexte/2017/7612},
  urn = {urn:nbn:de:0030-drops-76122},
  doi = {10.4230/LIPIcs.SEA.2017.24},
  arxiv = {1606.00484},
  annote = {Keywords: Selection Problem, Quickselect, Median of Medians, Algorithm Engineering, Algorithmic Libraries}
}