Quicksort with unreliable comparisons: a probabilistic analysis

2003/12/24 by L. Alonso, Alonso, L., P. Chassaing +9
Mathematics · #60F05 (Primary) 68P10 #68M15 (Secondary) #FOS: Mathematics #Probability (math.PR) #math.PR #msc:60F05 #msc:68M15 #msc:68P10

paper · pdf · doi:10.48550/arxiv.math/0312437

29 pages, 3 figures

arxiv created 2003/12/24 · arxiv updated 2009/12/01

Abstract

We provide a probabilistic analysis of the output of Quicksort when comparisons can err.

Related

• A numerical analysis of Quicksort: How many cases are bad cases?
• The number of bit comparisons used by Quicksort: an average-case analysis
• The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract)
• Variance of the number of Comparisons of Randomized Quicksort
• Using Non-Linear Difference Equations to Study Quicksort Algorithms