QUICKSORT WITH UNRELIABLE COMPARISONS: A PROBABILISTIC ANALYSIS

ar X iv :m at h. PR /0 31 24 37 v 1 2 4 D ec 2 00 3 QUICKSORT WITH UNRELIABLE COMPARISONS: A PROBABILISTIC ANALYSIS LAURENT ALONSO, PHILIPPE CHASSAING, FLORENT GILLET, SVANTE JANSON, EDWARD M. REINGOLD, AND RENE SCHOTT Abstract. We provide a probabilistic analysis of the output of Quicksort when comparisons can err. 1. Introduction Suppose that a sorting algorithm, knowingly or unknowingly, uses element com- parisons that can err. Considering sorting algorithms based solely on binary com- parisons of the elements to be sorted (algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when those comparisons are unreliable? For example, [6] gives a clever O ( ??1 logn ) algorithm to assure, with probability 1? ?, that a putatively sorted sequence of length n is truly sorted. But knowing the structure of the ill-sorted output would likely make error checking eas- ier. Also, in situations in which a reliable comparison is the fruit of a long process, one could chose to interupt the comparison process, thus trading reliability of com- parisons (and quality of the output) for time. As a first step in order to understand the consequences of errors, we propose to analyze the number of inversions in the output of a sorting algorithm (we choose Quicksort [10]) subject to errors.

• comparisons can


• poisson point


• let ?


• always let


• nu elements


• poisson random variable


• poisson process


• elements being


• being equiprobable


• unreliable comparisons