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

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.

• 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