Quicksort with Unreliable Comparisons: A Probabilistic Analysis

DOI10.1017/S0963548304006297MaRDI QIDQ4670351zbMATH OpenOpenAlexFDO

Authors L. Alonso, Philippe Chassaing, Florent Gillet, Svante Janson, Edward M. Reingold, R. Schott

Publication date 18 April 2005

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

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

Cited in

(7)

• Optimal dislocation with persistent errors in subquadratic time
• Optimal dislocation with persistent errors in subquadratic time
• Optimal sorting with persistent comparison errors
• Sorting with Recurrent Comparison Errors
• Energy efficient sorting, selection and searching
• Recursive merge sort with erroneous comparisons
• Energy efficient sorting, selection and searching

This page was built for publication: Quicksort with Unreliable Comparisons: A Probabilistic Analysis

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