| | |
There is another way to find the average comparison cost for quicksort that involves something called the linearity of expected value. Students having taken a course in probability and statistics may recognize this property, but here's the nutshell version -- first, imagine you have 3 envelopes:
Suppose further that they are each stuffed with some amount of cash, as they are birthday gifts from three of your relatives: Aunt Alice, Uncle Bob, and Grandpa Chuck. The cash gifts you have received from these three relatives have varied in the past, but Aunt Alice's average gift amount is $\$30$, Uncle Bob's average gift is $\$50$, and Grandpa Chuck's average gift is $\$10$. Even though the envelopes haven't yet been opened, can you form an expectation for the average total amount of money you will receive? Of course you can! You anticipate getting a grand total of $\$90$. How did you form this expectation? You just added together the amounts you expected from each person, of course. This intuitive result is something guaranteed by the aforementioned linearity -- that the expectation for a sum can be written as a sum of separate expectations.
Here, we are interested in the average (i.e., expected) total number of comparisons in a quicksort of $n$ items in some array. Let $i$ and $j$ represent the positions of two distinct elements, $z_i$ and $z_j$ in the sorted array. That is to say, when the quicksort has concluded, we have the sequence of values $z_1 \lt z_2 \lt z_3 \lt \cdots \lt z_n$, and $i$ and $j$ are two indices in this list. We also insist that $z_j$ be to the right of $z_i$ in this sorted list. Thus, $1 \le i \lt j \le n$.
Now suppose we have an envelope for every possible pair $i,j$. Notably, these envelopes then represent all possible comparisons that could be made. There is $\$1$ in every such envelope corresponding to an $i,j$ pair where $z_i$ was compared with $z_j$ in the course of the quicksort, and $\$0$ in all of the other envelopes. Since in applying the quicksort algorithm (with "left-to-right" partitioning), any two elements are compared at most once, we can see that the total number of comparisons made must then equal the total amount of money in the envelopes.
In this way, we have made the amount of money in each envelope dependent on how the quicksort progressed. This, of course, depends on the initial permutation of the elements $z_1$ through $z_n$ in the array before the quicksort began. For now then, let us just denote the value in the envelope corresponding $i,j$ by $X_{ij}$.
Letting $X$ be the total amount of money in all of the envelopes (and consequently, the total number of comparisons made), we then have
$$X = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} X_{ij}$$To see this, note that since $i$ and $j$ are integers with $i \lt j$, it must be the case that both $j \ge i+1$ and $i \le n-1$. (Note, if $i=n$ there is no room left for $j$.)
Let us now denote the expected total amount of money in all of the envelopes (and consequently, the average number of comparisons made during the quicksort) by $E[X]$, and similarly denote the expected value for $X_{ij}$ with $E[X_{ij}]$. Using the previously described linearity, the expected value of $X$ (a sum) must be equal to the sum of these individual expected values: $$E[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} E[X_{ij}]$$
Notice that each of these individual expected values $E[X_{ij}]$ is identical to the probability that the elements $z_i$ and $z_j$ are compared. As an aid in finding that probability, let us consider the following concrete example first...
Suppose we are performing a quicksort (using "left-to-right" partitioning) on the numbers $1$ through $10$ (any order), and the first pivot chosen ends up being $7$. The first partition will then separate these numbers into two sets $\{1,2,3,4,5,6\}$ and $\{8,9,10\}$. Note that the pivot, $7$, is compared exactly once with all of the other elements. However, no number from the first set (e.g., $2$) is or ever will be compared to any number from the second set (e.g., $9$).
More generally, consider the group of values $z_i,z_{i+1},z_{i+2},\ldots,z_j$, taken from $z_1,z_2,\ldots,z_n$ mentioned earlier. If the first pivot chosen among this group is neither $z_i$ or $z_j$, then the elements $z_i$ and $z_j$ are never compared to each other (similar to how the $2$ and $9$ were never compared to each other when the pivot $7$ was chosen in our earlier example).
However, if $z_i$ is the first pivot chosen from this group, then the elements $z_i$ and $z_j$ will be compared (just like the $7$ was compared with everything but itself in our earlier example). Likewise, if $z_j$ is the first pivot chosen from this group, then the elements $z_i$ and $z_j$ again are compared.
Noting that there are $(j-i+1)$ values in the group $\{z_i,z_{i+1},z_{i+2},\ldots,z_j\}$, and upon considering the choice of the first pivot from this group (a choice which happens randomly and independently in the quicksort algorithm) only $2$ of them will result in $z_i$ and $z_j$ being compared, we have the probability $z_i$ and $z_j$ are compared (and the expected value of $X_{ij}$) given by $$E[X_{ij}] = \frac{2}{j-i+1}$$ Substituting this into our earlier expression, this makes the average total number of comparisons made in the quicksort of $n$ items equal to $$E[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j-i+1}$$ We can simplify the inner sum by expressing it in terms of $k=j-i$, and then pull the factor of $2$ in the numerator out of both summations to obtain $$E[X] = 2\sum_{i=1}^{n-1} \sum_{k=1}^{n-i} \frac{1}{k+1}$$ With a goal of using big-oh notation to describe the average comparison cost for the quicksort of $n$ items, we now seek a convenient upper bound on this expression. Note that decreasing each denominator of $k+1$ to $k$ above will only make the positive fractions involved larger. Adding more (positive) terms corresponding to $k \gt n-i$ will do the same. As such, we have bound the total number of comparisons with $$E[X] \lt 2\sum_{i=1}^{n-1} \sum_{k=1}^{n} \frac{1}{k}$$ Appealing to calculus, as we did in the first analysis of the comparison cost for quicksort, we note that the inner sum of $\sum_{k=1}^n (1/k)$ can be approximated by the integral $\int_1^n (1/x)\,dx$ and is thus $O(\ln n)$.
This tells us that $E[X]$ is $$2\sum_{i=1}^{n-1} O(\ln n) = O(n \ln n)$$ So the average total number of comparisons made in a quicksort is $O(n \ln n)$.
QED.