# Analysis of sorting Algorithm with probably wrong comparator? [duplicate]

This question already has an answer here:

It is an interesting question from an Interview, I failed it.

An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order).

We have a comparator $C$, but it has a probability p to return correct results.

Now we use $C$ to implement sorting algorithm (any kind, bubble, quick etc..)

After sorting we have $[A_{i_1}, A_{i_2}, \ldots, A_{i_n}]$ (It could be wrong)

Now given a number $m$ ($m < n$), the question is as follows:

1. What is Expectation of size $S$ of Intersection between $\{A_1, A_2, \ldots, A_m \}$ and $\{A_{i_1}, A_{i_2}, \ldots, A_{i_m} \}$, in other words, what is $E[S]$?

2. Any relationship among $m$, $n$ and $p$ ?

3. If we use different sorting algorithm, how will $E[S]$ change?

My idea is as follows:

1. When $m=n$, $E[S] = n$, surely
2. When $m=n-1$, $E[S] = n-1+P(A_n \text{ in } A_{i_n})$

I dont know how to complete the answer but I thought it could be solved through induction.. Any simulation methods would also be fine I think.

## marked as duplicate by Raphael♦Aug 18 '15 at 8:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Try to work out $m=1$ and selection sort, which is asking for the probability that the smallest element ends up first. – Louis Apr 26 '15 at 14:50
• – Raphael Apr 28 '15 at 17:09
• I'd imagine the answer might depend upon which sorting algorithm you are using (no?), so in questions 1 and 2 you should probably tell us which sorting algorithm you're asking about. Also, do you mean that if we use the comparator $k$ times, then all $k$ events are independent? For instance, if I use the comparator to compare $A_1$ to $A_2$, and then I compare those same two elements again, are the two results independent? – D.W. May 2 '15 at 1:37

## 1 Answer

The question seems ill-defined. A faulty/probabilistic comparator will have a radically different impact on different sort algorithms. Each algorithm will have a different, and potentially very complex, analysis.

One possibly interesting note is that you will get exactly reverse sort order when p=0. When p=0.5 the result will be unbiased on ascending vs descending, but the resulting permutations will not be equally likely.

• Welcome to CS Stack Exchange! This seems to be more of a comment than an answer (when you have a little more reputation, you'll be able to post comments) but I agree that the question is ill-defined. As a new user, it's probably best to give your attention to well-defined questions so you can pick up enough reputation from upvotes to leave comments. – David Richerby Aug 18 '15 at 10:00