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

average computing timehigher moments of computingQUICKSORTsorting

Mathematics Subject Classification ID

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

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

• A limiting distribution for quicksort
• 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?)

Cited in

(25)

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

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)