Combinatorial analysis of quicksort algorithm

DOI10.1051/ITA/1989230303171MaRDI QIDQ4203824zbMATH OpenOpenAlexFDO

Authors Paul-Louis Hennequin

Publication date 1989

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92337

zbMATH Keywords

sortingaverage computing timehigher moments of computingQUICKSORT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Searching and sorting (68P10)

Recommendations

• How Many Comparisons Does Quicksort Use?
• QuickXsort: a fast sorting scheme in theory and practice
• A limit theorem for “quicksort”
• Asymptotic analysis of an optimized quicksort algorithm.
• QuickHeapsort, an efficient mix of classical sorting algorithms

Cites work

• scientific article; zbMATH DE number 3959436 (Why is no real title available?)
• scientific article; zbMATH DE number 3508512 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3349816 (Why is no real title available?)
• A limiting distribution for quicksort

Cited in

(25)

• Analysis of quickselect : an algorithm for order statistics
• Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
• Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates
• Using nonlinear difference equations to study Quicksort algorithms
• Maximum selection and sorting with adversarial comparators
• A limit theorem for “quicksort”
• scientific article; zbMATH DE number 1984552 (Why is no real title available?)
• A select and insert sorting algorithm
• General combinatorial schemas: Gaussian limit distributions and exponential tails
• Some properties of a limiting distribution in Quicksort
• A note concerning the limit distribution of the quicksort algorithm
• Analysis of Branch Misses in Quicksort
• Partial Quicksort and Quickpartitionsort
• An intuitive and simple bounding argument for Quicksort
• Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
• Logarithmic integrals, zeta values, and tiered binomial coefficients
• Transitional behaviors of the average cost of quicksort with median-of-\((2t+1)\)
• On a multivariate contraction method for random recursive structures with applications to quicksort
• Phase changes in random m-ary search trees and generalized quicksort
• A limiting distribution for quicksort
• Asymptotic analysis of an optimized quicksort algorithm.
• QuickXsort: a fast sorting scheme in theory and practice
• Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort
• How Many Comparisons Does Quicksort Use?
• Automatic average-case analysis of algorithms

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: Combinatorial analysis of quicksort algorithm

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