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

Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review

Autoren

  • Rudolf Grübel

Organisationseinheiten

Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Seiten (von - bis)177-192
Seitenumfang16
FachzeitschriftTheoretical Informatics and Applications
Jahrgang33
Ausgabenummer2
PublikationsstatusVeröffentlicht - März 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 Sachgebiete

Zitieren

On the median-of-k version of Hoare's selection algorithm. / Grübel, Rudolf.
in: Theoretical Informatics and Applications, Jahrgang 33, Nr. 2, 03.1999, S. 177-192.

Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review

Grübel R. On the median-of-k version of Hoare's selection algorithm. Theoretical Informatics and Applications. 1999 Mär;33(2):177-192. doi: 10.1051/ita:1999112
Grübel, Rudolf. / On the median-of-k version of Hoare's selection algorithm. in: Theoretical Informatics and Applications. 1999 ; Jahrgang 33, Nr. 2. S. 177-192.
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 -