Towards a Realistic Analysis of Some Popular Sorting Algorithms

DOI10.1017/S0963548314000649zbMath1371.68059MaRDI QIDQ5364228

Julien Clément, Brigitte Vallée, Thieu Hoa Nguyen Thi

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Related Items (3)

Towards a realistic analysis of the QuickSelect algorithm ⋮ Gaussian Distribution of Trie Depth for Strongly Tame Sources ⋮ Dichotomic Selection on Words: A Probabilistic Analysis

Cites Work

• Mellin transforms and asymptotics: Harmonic sums
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• On decay of correlations in Anosov flows
• Analytical depoissonization and its applications
• Special issue: Average-case analysis of algorithms
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Dynamical sources in information theory: A general analysis of trie structures
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Information theory: Sources, Dirichlet series, and realistic analyses of data structures
• Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Prevalence of rapid mixing in hyperbolic flows
• Gaussian Distribution of Trie Depth for Strongly Tame Sources
• The Ubiquitous Digital Tree
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Towards a Realistic Analysis of Some Popular Sorting Algorithms