I haven’t done a math post in a long while, and a probability post ever, so why not have a twofer?
First a little probability intro:
Sometimes we want to find the average value, usually called the “expected value”, of some random process. There’s a more intuitive way to ask about expected values: Which outcome is most likely? In other words, given the probabilities of multiple events happening, which event will tend to happen most? For instance, you might want to compute the average hand of poker.
In the single random variable case, the expected value looks like this:
…where is the numerical value of the random outcome , and is the probability that that outcome will occur.
Now let’s turn to the Quicksort algorithm. You can find more here, but I’ll explain the basic idea.
Quicksort, as its name implies, is an algorithm that will sort a list of things. In reality, it can sort a variety of different objects according to a variety of rules, but for simplicity we’ll do one that puts a list of numbers in increasing order.
Here’s how a random numerical Quicksort works. Take a list of distinct numbers at random (i.e. their positions are important). So let’s make this our list:
Take one of these values at random, and fix its position. This will separate our list into two sublists. Say we pick 8. Then, put all of the values less than 8 into the list to the left of 8 (by convention) and all of those greater than 8 in the list to the right. In other words, compare the chosen value with all of the unchosen values. That gives:
Now, take the leftmost list, and if it contains more than one value, choose a value at random from it and repeat this process. Say we choose 2. That gives:
We can start to see that in a few more iterations, this process will numerically sort the list from smallest to largest.
Something that really bugs computer scientists about algorithms is how fast they work. Speed is an important practical factor (and there are a few others, computational power for instance) when deciding to use one algorithm over another. If it works too slowly, it impinges on productivity of the computer and its user. So we’re going to discuss how quick Quicksort actually is, using expected value. In other words, we’re going to derive how many comparisons Quicksort makes on an arbitrarily large list of numbers.
How do we know when two numbers and have been compared, and how can we track it? As is usual, we set up an indicator function. The indicator function will track how many comparisons are made. For convenience, we’ll number the numbers (so to speak) by their size. So “1” will stand for the smallest number, “2” for the next smallest, etcetera. Here’s the indicator function:
Since our list has numbers in it, our random variable will be:
It’s easier to see why this summation works if you write it out. The numbers which actually compare under the indicator mapping will be counted, and the ones that don’t will be zeroed out. So in the end we’ll get the number of total comparisons.
So then it follows that the expected value is:
(The mapping can go inside the summation; this is easy to derive)
But, from our definition of expected value and the indicator function, this resolves to:
, where again, is the probability mapping.
Well, the probability that and are compared is just . Thus we get:
Let’s assume, now, that our list contains a lot of numbers. Otherwise, it wouldn’t really matter how fast it went (a list of five numbers is trivial to sort, for instance). Then we can approximate these summations with integrals, and we get:
, which is usually written .
So Quicksort requires on average comparisons in order to sort a list numbers long. Factoring in how much time it takes to make each comparison (which isn’t much), you can easily estimate the average amount of time it takes to sort a list with Quicksort!
So, whipping out my calculator, a list of 5000 numbers would take, on average, about 85172 comparisons. Remember, choosing the comparison numbers is random, so the amount of comparisons will vary. According to Wikipedia, when Quicksort does its worse, it takes about comparisons (more on Big-O notation here), whereas the average is . (Remember, increases MUCH more slowly than . Which means is horrible in comparison! )