Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T02:28:46.368Z Has data issue: false hasContentIssue false

Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect

Published online by Cambridge University Press:  22 February 2016

James Allen Fill*
Affiliation:
Johns Hopkins University
Takehiko Nakama*
Affiliation:
Johns Hopkins University
*
∗ Postal address: Department of Applied Mathematics and Statistics, Johns Hopkins University, 3400 N. Charles Street, Baltimore, MD 21218-2682, USA. Email address: jimfill@jhu.edu
∗∗ Current address: European Centre for Soft Computing, Edificio de Investigación, Calle Gonzalo Gutiérrez Quirós S/N, 33600 Mieres, Asturias, Spain.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

When the search algorithm QuickSelect compares keys during its execution in order to find a key of target rank, it must operate on the keys' representations or internal structures, which were ignored by the previous studies that quantified the execution cost for the algorithm in terms of the number of required key comparisons. In this paper we analyze running costs for the algorithm that take into account not only the number of key comparisons, but also the cost of each key comparison. We suppose that keys are represented as sequences of symbols generated by various probabilistic sources and that QuickSelect operates on individual symbols in order to find the target key. We identify limiting distributions for the costs, and derive integral and series expressions for the expectations of the limiting distributions. These expressions are used to recapture previously obtained results on the number of key comparisons required by the algorithm.

Information

Type
General Applied Probability
Copyright
© Applied Probability Trust