Quicksort with unreliable comparisons: a probabilistic analysis

Laurent Alonso (1) , Philippe Chassaing (2) , Florent Gillet (2) , Svante Janson (3) , Edward M. Reingold (4) , René Schott (1)

1 ISA - Models, algorithms and geometry for computer graphics and vision
2 IECN - Institut Élie Cartan de Nancy
3 Department of Mathematics [Uppsala]
4 IIT CS - Department of Computer Science [IIT]

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

Domaines: Probabilités [math.PR]

Laurent Alonso, Philippe Chassaing, Florent Gillet, Svante Janson, Edward M. Reingold, et al.. Quicksort with unreliable comparisons: a probabilistic analysis. Combinatorics, Probability and Computing, 2004, 13 (4-5), pp.419-449. ⟨10.1017/S0963548304006297⟩. ⟨hal-00005087⟩