Distributional convergence for the number of symbol comparisons used by QuickSelect

DOI10.1239/AAP/1370870125zbMATH Open1278.68354arXiv1202.2599OpenAlexW3104914883MaRDI QIDQ2837754FDOQ2837754

Authors: James Allen Fill, Takehiko Nakama 

Publication date: 11 July 2013

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1202.2599

Recommendations

• Distributional convergence for the number of symbol comparisons used by QuickSort
• Distributional convergence for the number of symbol comparisons used by QuickSort (extended abstract)
• Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find
• Towards a realistic analysis of the QuickSelect algorithm

zbMATH Keywords

limit distributionalmost-sure convergenceprobabilistic sourceL\(^p\)-convergenceQuickQuantQuickSelectQuickValsymbol comparison

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) (L^p)-limit theorems (60F25)

Cites Work

• Title not available (Why is that?)
• The contraction method for recursive algorithms
• Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Quickselect and the Dickman Function
• Hoare's Selection Algorithm: A Markov Chain Approach
• Analysis of quickselect : an algorithm for order statistics
• Asymptotic distribution theory for Hoare's selection algorithm
• A limit theorem for “quicksort”
• Multiple Quickselect -- Hoare's Find algorithm for several elements
• Dynamical sources in information theory: A general analysis of trie structures
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Title not available (Why is that?)
• The number of bit comparisons used by quicksort: an average-case analysis
• A limiting distribution for quicksort
• Title not available (Why is that?)
• On the probabilistic worst-case time of ``find
• Exponential bounds for the running time of a selection algorithm
• Probabilistic analysis of multiple quick select
• The moments of FIND

Cited In (12)

• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm
• Towards a realistic analysis of the QuickSelect algorithm
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Analysis of the expected number of bit comparisons required by quickselect
• Distributional convergence for the number of symbol comparisons used by QuickSort (extended abstract)
• Multikey quickselect
• Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find
• Towards a realistic analysis of some popular sorting algorithms
• Density functions for \texttt{QuickQuant} and \texttt{QuickVal}
• The analysis of range quickselect and related problems
• Process convergence for the complexity of radix selection on Markov sources

Uses Software

• Find

This page was built for publication: Distributional convergence for the number of symbol comparisons used by QuickSelect

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2837754)