Distributional convergence for the number of symbol comparisons used by QuickSelect
From MaRDI portal
Publication:2837754
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.
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
Cites work
- scientific article; zbMATH DE number 3513051 (Why is no real title available?)
- scientific article; zbMATH DE number 765034 (Why is no real title available?)
- scientific article; zbMATH DE number 3405492 (Why is no real title available?)
- A limit theorem for “quicksort”
- A limiting distribution for quicksort
- Analysis of quickselect : an algorithm for order statistics
- Asymptotic distribution theory for Hoare's selection algorithm
- Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
- Distributional convergence for the number of symbol comparisons used by QuickSort
- Dynamical sources in information theory: A general analysis of trie structures
- Exponential bounds for the running time of a selection algorithm
- Hoare's Selection Algorithm: A Markov Chain Approach
- Multiple Quickselect -- Hoare's Find algorithm for several elements
- On the probabilistic worst-case time of ``find
- Probabilistic analysis of multiple quick select
- Quickselect and the Dickman Function
- The Number of Symbol Comparisons in QuickSort and QuickSelect
- The contraction method for recursive algorithms
- The moments of FIND
- The number of bit comparisons used by quicksort: an average-case analysis
Cited in
(11)- Distributional convergence for the number of symbol comparisons used by QuickSort
- Multikey quickselect
- Towards a realistic analysis of the QuickSelect algorithm
- Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm
- The Number of Symbol Comparisons in QuickSort and QuickSelect
- Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find
- Density functions for \texttt{QuickQuant} and \texttt{QuickVal}
- Process convergence for the complexity of radix selection on Markov sources
- Distributional convergence for the number of symbol comparisons used by QuickSort (extended abstract)
- Towards a realistic analysis of some popular sorting algorithms
- The analysis of range quickselect and related problems
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)
