Analysis of a sorting algorithm with a likely wrong comparator?

Question

This is an interesting question from the interview, I failed it.

The array has n different elements [A1 .. A2 .... An] (random order).

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

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

After sorting, we have [Ai1, Ai2, ..., Ain] (This may be wrong) .

Now, given the number m (m <n), the question is:

• What is the Waiting for size S intersection between {A1, A2, ..., Am} and {Ai1, Ai2, ..., Aim}, in other words, what is E [S] ?

• Any relationships among m, n and p ?

• If we use a different sorting algorithm , how will E [S] change ?

My idea is this:

• When m = n, E [S] = n, surely
• When m = n-1, E [S] = n-1 + P (An in Ain)

I do not know how to complete the answer, but I thought that this could be solved by induction. Any modeling techniques would also be good, I think.

Answer 1

Hm, A1, A2,..., An ( ), C . , m, {A1,..., An}.

, S k, (m k)*((n-m) (n-k))/(n m), (a b) "a b", , b a. ( k m-k .)

E [S] - sum(0 <= k <= m) k*(m k)*((n-m) (n-k))/(n m), m/(n m) * sum(0 <= k <= m) ((m-1) (k-1))*((n-m) (n-k)). () , ((n-1) (m-1)), , , m/(n m) * ((n-1) (m-1))= m^2/n.

Answer 2

:

• , Ai1,..., Aim () , m Aj1,..., Ajn. ( ).
• , C .
• , n = 2 ^ N.

• = 1
• sorting-algorithm = merge sort

Aj1 - . ld (n) = N . , ld (n) = N. , P (Ai1 = Aj1) = p ^ N, m = 1 E [S]. ,

E[S] = p^ld(n)

• = 1
• sorting-algorithm =

k (Ak = Aj1), max (k-1,1) , Ak (Ak = Ai1). n ,

E[S] = P(Ai1=Aj1) = 
     = P(Ai1=Aj1|Aj1=A1)*P(Aj1=A1) + ... + P(Ai1=Aj1|Aj1=An)*P(Aj1=An) =
     = 1/n (p + p + p^2 + ... + p^(n-1)) = 1/n ((1-p^(n-1))/(1-p)+p-1) =
     = (2p - p^2 - p^(n-1)) / (n(1-p))

!