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

Question

This question already has answers here:

Sorting algorithms which accept a random comparator (4 answers)

Closed 10 years ago.

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.

• Louis: Try to work out $m=1$ and selection sort, which is asking for the probability that the smallest element ends up first.
• Raphael: Related question.
• D.W.: 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?

Answer 1

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.

• David Richerby: 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.