On the median-of-k version of Hoare's selection algorithm

Research output: Contribution to journal › Article › Research › peer review

Authors

  • Rudolf Grübel

Research Organisations

View graph of relations

Details

Original languageEnglish
Pages (from-to)177-192
Number of pages16
JournalTheoretical Informatics and Applications
Volume33
Issue number2
Publication statusPublished - Mar 1999

Abstract

In Hoare's (1961) original version of the algorithm FIND the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.

ASJC Scopus subject areas

Cite this

On the median-of-k version of Hoare's selection algorithm. / Grübel, Rudolf.
In: Theoretical Informatics and Applications, Vol. 33, No. 2, 03.1999, p. 177-192.

Research output: Contribution to journal › Article › Research › peer review

Grübel R. On the median-of-k version of Hoare's selection algorithm. Theoretical Informatics and Applications. 1999 Mar;33(2):177-192. doi: 10.1051/ita:1999112
Download
@article{08cc3bcaa6ab462a966c0cf10b658068,
title = "On the median-of-k version of Hoare's selection algorithm",
abstract = "In Hoare's (1961) original version of the algorithm FIND the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.",
author = "Rudolf Gr{\"u}bel",
year = "1999",
month = mar,
doi = "10.1051/ita:1999112",
language = "English",
volume = "33",
pages = "177--192",
journal = "Theoretical Informatics and Applications",
issn = "0988-3754",
publisher = "EDP Sciences",
number = "2",

}

Download

TY - JOUR

T1 - On the median-of-k version of Hoare's selection algorithm

AU - Grübel, Rudolf

PY - 1999/3

Y1 - 1999/3

N2 - In Hoare's (1961) original version of the algorithm FIND the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.

AB - In Hoare's (1961) original version of the algorithm FIND the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.

UR - http://www.scopus.com/inward/record.url?scp=0343826140&partnerID=8YFLogxK

U2 - 10.1051/ita:1999112

DO - 10.1051/ita:1999112

M3 - Article

AN - SCOPUS:0343826140

VL - 33

SP - 177

EP - 192

JO - Theoretical Informatics and Applications

JF - Theoretical Informatics and Applications

SN - 0988-3754

IS - 2

ER -