How Many Comparisons Does Quicksort Use?

DOI10.1006/JAGM.1995.1044MaRDI QIDQ4857539zbMATH OpenOpenAlexFDO

Authors William F. Eddy, M. J. Schervish

Publication date 11 April 1996

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1995.1044

zbMATH Keywords

Quicksort sorting algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• The Number of Symbol Comparisons in QuickSort and QuickSelect
• The number of bit comparisons used by quicksort: an average-case analysis
• The number of bit comparisons used by Quicksort, an average-case analysis
• How good is multi-pivot quicksort?
• Quicksort revisited
• Quicksort asymptotics
• The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract).
• Combinatorial analysis of quicksort algorithm

Cited in

(10)

• Some properties of a limiting distribution in Quicksort
• Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
• Approximating the limiting quicksort distribution
• The Worst Case Permutation for Median-of-Three Quicksort
• Combinatorial analysis of quicksort algorithm
• scientific article; zbMATH DE number 1052336 (Why is no real title available?)
• scientific article; zbMATH DE number 742989 (Why is no real title available?)
• Using nonlinear difference equations to study Quicksort algorithms
• Quicksort is optimal for many equal keys
• The number of bit comparisons used by Quicksort, an average-case analysis

This page was built for publication: How Many Comparisons Does Quicksort Use?

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