This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications".
The quick sort is an efficient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm begins by taking the first element $a_1$ and forming two sublists, the first containing those elements that are less than $a_1$, in the order they arise, and the second containing those elements greater than $a_1$, in the order they arise. Then $a_1$ is put at the end of the first sublist. This procedure is repeated recursively for each sublist, until all sublists contain one item. The ordered list of $n$ items is obtained by combining the sublists of one item in the order they occur.
In this exercise we find the average-case complexity of the quick sort algorithm, assuming a uniform distribution on the set of permutations.
a) Let X be the number of comparisons used by the quick sort algorithm to sort a list of n distinct integers. Show that the average number of comparisons used by the quick sort algorithm is $E(X)$ (where the sample space is the set of all $n!$ permutations of $n$ integers).
b) Let $I(j,k)$ denote the random variable that equals 1 if the $j^{th}$ smallest element and the $k^{th}$ smallest element of the initial list are ever compared as the quick sort algorithm sorts the list and equals 0 otherwise. Show that $X = \sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}$.
c) Show that $E(X) = \sum_{k=2}^{n} \sum_{j=1}^{k-1} p$, where $p$ is the probability that the $j^{th}$ smallest element and the $k^{th}$ smallest element are compared.
d) Show that $p$ (the $j^{th}$ smallest element and the $k^{th}$ smallest element are compared), where $k > j$, equals $2/(k − j + 1)$.
I didn't have any particular problem with parts a, b and c.
I think that I managed to understand parts a, b and c.
For part a, this seems obvious from the definition of expected value. E(X) is the average value of the number of comparisons, weighted by the probability that the permutation has a particular order (which is $1/n!$).
For part b, I verified that the sum $\sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}$ gives $I_{1,2} + I_{1,3} + I_{2,3} + I_{1,4} + I_{2,4} + I_{3,4}+\cdots+I_{n-1,n}$, that is, it gives the value of $I_{j,k}$ for every combination of $j$ and $k$. So, it sums 1 to every pair of integers that will be compared. Since the only situation two integers get compared is when one of them the the first element of the list (also called the "pivot"), this means that these two integers will go each one to separate sublists, so that they will not be compared anymore (in other words, every pair of integers is compared at most once). Therefore, it makes sense to say that the mentioned sum will give $X$, the total number of comparisons made by quick sort.
Part c also seems straightforward. The result follows from the linearity of the expected value (the expected value of a sum is the sum of the expected values): $E(X) = E\left(\sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}\right) = \sum_{k=2}^{n}\sum_{j=1}^{k-1}E(I_{j,k})$. The value of $E(I_{j,k})$ (the expected value of $I_{j,k}$) is 1 times the probability that $I_{j,k}$ gets the value 1; the probability that $I_{j,k}$ gets the value 1 is the probability that the $j^{th}$ smallest element and the $k^{th}$ smallest element are compared, so $I_{j,k} = p$. So, $E(X) = \sum_{k=2}^{n}\sum_{j=1}^{k-1}p$.
Part d is where I got stuck.
I tried to reason the following way: given a list that will be ordered by quick sort, two integers $a_j$ and $a_k$ will get compared only if one of them is the pivot. Also, if a number that is smaller than $a_k$ and greater than $a_j$ is the pivot, $a_k$ and $a_j$ will go to separate sublists, so that they will never get compared. Otherwise, if the pivot is either greater than both $a_k$ and $a_j$, or smaller than them, $a_j$ and $a_k$ will both go to the same sublist, so that, in another recursive call of the algorithm, they may still get compared.
But I'm not sure how to show that the probability that the $j^{th}$ smallest element and the $k^{th}$ smallest element are ever compared is $2/(k − j + 1)$. Could anyone give a hint? I would prefer a hint over a complete solution, so that I can discuss it further in comments to fill in the holes.
Best Answer
Consider the set $z_{i,j} = \{z_i,z_{i+1},....,z_{j-1},z_j\}$ This set order is in terms of the values (not the order in the Array) i.e. $z_i<z_j \;and\; j>i$. As long as none of the these are chosen as pivot,all are passed to the same recursive call.
i.e. pivot $\leftarrow$ x
$x > z_{j} or \; x<z_{i}$ , $z_{i,j}$ is passed to same recursive call.
Consider the case when either of $z_{i},...z_{j} $ gets chosen as pivot.
a) if $z_i$ or $z_j$ gets chosen first, then $z_i$ and $z_j$ get compared.
b) if one of the $z_{i+1} ... z_{j-1}$ gets chosen first,then $z_i$ and $z_j$ are never compared.
$Pr\{z_i z_j compared\} = Pr\{X=z_i\} + Pr\{X=z_j\}$
PS: $Pr\{X=z_i\} = Pr\{X=z_j\} = 1/(j-i+1)$
I hope it helps.