The Number of Symbol Comparisons in QuickSort and QuickSelect

DOI10.1007/978-3-642-02927-1_62zbMath1248.68181OpenAlexW1593253629MaRDI QIDQ3638078

Brigitte Vallée, James Allen Fill, Julien Clément, Philippe Flajolet

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_62

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (12)

Towards a realistic analysis of the QuickSelect algorithm ⋮ Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme ⋮ Gaussian Distribution of Trie Depth for Strongly Tame Sources ⋮ Towards a Realistic Analysis of Some Popular Sorting Algorithms ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ Generic properties of subgroups of free groups and finite presentations ⋮ Analysis of the expected number of bit comparisons required by quickselect ⋮ Process convergence for the complexity of radix selection on Markov sources ⋮ Multikey quickselect ⋮ Analysis of swaps in radix selection ⋮ Dichotomic Selection on Words: A Probabilistic Analysis ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect

This page was built for publication: The Number of Symbol Comparisons in QuickSort and QuickSelect