Using nonlinear difference equations to study Quicksort algorithms

DOI10.1080/10236198.2020.1720665MaRDI QIDQ4960142zbMATH OpenOpenAlexFDO

Authors Yukun Yao

Publication date 9 April 2020

Published in Journal of Difference Equations and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.00118

zbMATH Keywords

difference equationrecurrence relationQuicksortexplicit expressionexperimental mathematics

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Symbolic computation and algebraic computation (68W30) Searching and sorting (68P10) Applications of difference equations (39A60)

Abstract: Using non-linear difference equations, combined with symbolic computations, we make a detailed study of the running times of numerous variants of the celebrated Quicksort algorithms, where we consider the variants of single-pivot and multi-pivot Quicksort algorithms as discrete probability problems. With non-linear difference equations, recurrence relations and experimental mathematics techniques, explicit expressions for expectations, variances and even higher moments of their numbers of comparisons and swaps can be obtained. For some variants, Monte Carlo experiments are performed, the numerical results are demonstrated and the scaled limiting distribution is also discussed.

Recommendations

• On some nonlinear recurrences that arise in computer science
• scientific article; zbMATH DE number 1052336
• How Many Comparisons Does Quicksort Use?
• On a multivariate contraction method for random recursive structures with applications to quicksort
• A limit theorem for “quicksort”

Cites work

• scientific article; zbMATH DE number 1375579 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2159646 (Why is no real title available?)
• A holonomic systems approach to special functions identities
• A note concerning the limit distribution of the quicksort algorithm
• Analysis of Hoare's FIND algorithm with Median-of-three partition
• Analysis of multiple quickselect variants.
• Asymptotic analysis of an optimized quicksort algorithm.
• Combinatorial analysis of quicksort algorithm
• DUAL PIVOT QUICKSORT
• Quicksort
• Symbolic moment calculus. I: Foundations and permutation pattern statistics
• Symbolic summation assists combinatorics
• The concrete tetrahedron. Symbolic sums, recurrence equations, generating functions, asymptotic estimates

Cited in

(1)

• On some nonlinear recurrences that arise in computer science

Describes a project that uses

Uses Software

• stCore
• Quicksort
• SMCper
• EKHAD
• HISTABRUT
• SIGMA

This page was built for publication: Using nonlinear difference equations to study Quicksort algorithms

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