Stooge sort: some more comments
Stooge sort’s time complexity is about O(n^2.7), whereas Bubble sort is O(n^2). This small change in exponent makes a big difference as shown in the video.
The proof of O(n^2.7) can be done in several ways. Here’s a simple, sketchy one:
Note that when we switched from 4 elements to 6 elements, the number of comparisons tripled. This is because for 6 elements stooge sort sorted three sublists of 4 elements. This happened again when we switched from 6 elements to 9 elements. Since now stooge sort sorted three sublists of 6 elements, again the total number of comparisons tripled. So we have a general rule: every time we increase the number of elements n by 50%, the number of comparisons is tripled.
Now let’s say f(n) is a function that tells us the number of comparisons stooge sort does for n elements. So our rule is: f(1.5 n)=3 f(n).
Let’s guess f(n)=n^a for some constant a. So now our rule is:
(1.5n)^a=3 n^a or
1.5^a n^a=3 n^a or
1.5^a = 3
Solving for a, we get a=log 3/log 1.5=~2.7.
Note also stooge sort is usually described with a slight difference that makes it even worse. Say it starts sorting a list of n elements. According to the usual description, it starts by checking if the first and last element are out of order, and if so, it swaps them. Only then, if n>2, it proceeds to the recursion part. In the video we kept this comparison and swapping only for lists of 2 elements, saving some obviously redundant actions.
Bogosort: some more comments
In the video, it takes Bogosort 345 trials to finish, and 605 comparisons. How typical is that?
Number of trials
For 6 elements, there are 720 different permutations. So the probability of success in each trial is 1/720. The probability of succeeding within 345 trials is 1-(719/720)^345=0.38, a little over a third. So Bogosort got a bit lucky in the video, but not too much.
Another way to see how typical it is, is to measure expectation. I.e., calculate the expected number of trials till success. In our case this is actually 720. This means if we’ll repeat the experiment of letting bogosort sort our list and compute the average number of trials it required, we’ll end up with 720.
One way to compute this expectation is as follows. Let E denote the expected number of trials. Say our probability of success in a single trial is p. I.e., in our case p=1/720. So with probabilty p the number of trials will be just one. With probability (1-p) the first trial will fail. Since lady luck has no memory, we expect to see E more trials from this point onward. So we have 1 trial with probability p, and (1+E) trials with probability (1-p). The expectation is the weighted average of these, so E=p+(1-p)(1+E). This easily simplifies to E=1/p. So, in our case E=720.
Number of comparisons per trial
In the video bogosort did 605/345=1.75 comparsions per trial. Is that typical? Given a random permutation, how many comparisons on avarage does it take to test if it is sorted or not?
A simple way to give an approximate answer is as follows. If the first comparison detects an out of order pair, we’ll call it a success. It has probabililty of 0.5 to succeed. If it ‘fails’ (the pair is correctly ordered), another comparison is needed. Simplifying things, we’ll say it too has probability 0.5 of success, and so on. Using the same computation as above, the expected number of comparisons needed till success is E=1/p, with p=0.5, so E=2.
This is larger than the actual figure we saw in the video, 1.75.
A more accurate calculation is as follows. It can be shown that the probability of requiring exactly k comparisons is k/(k+1)! The expected number of comparisons is a weighted average of the possible numbers of comparison 1..n-1, weighted by their probabilities, or the sum of k^2/(k+1)! with k running from 1 till n-1, with n being the number of elements. For large n this converges to Euler’s number e=2.718… minus 1, or about 1.718.
For n=6 we can compute it more accuratly to be 1.71. So in the video Bogosort did slightly more comparisons than the expected average.
How the shuffling works
The last segment of the video explains how to randomly shuffle a list. It skips one part though: how to randomly select an element from the list.
This is usually done using pseudorandom number generation.
We start from some seed number, say 123.
Each time we want to produce a pseudorandom number we run our current number x through some formula. An example formula can be: f(x)=(x*22695477+1) mod 4294967296. The “mod” operator is “modulus”, the remainder of integer division (for example, 10 mod 4 = 2)
So in our example, starting from x=123, the first pseudorandom number would be f(123)=2791543672. To get the second number, we’ll run this last result through f(), obtaining: f(2791543672)=431757273, and so on . . .
The first twelve numbers we get this way are: 2791543672, 431757273, 3732868590, 2587387463, 1489817268, 682206021, 3323974474, 1224428115, 551136560, 850754289, 4106346982, 265541791. They are not really random because we produced them using a deterministic formula f(). But they are pseudorandom, since statistically speaking the exhibit similar properties to a random stream of numbers.
If we want to randomly select elements from a list of 10 elements, we’ll produce a pseudorandom number x using a method similar to the one described above, then compute (x mod 10) to obtain a number in the range 0…9. This basically means to take the lowest decimal digit. So if we take the sequence of 12 numbers above, the first digits of each are: 2, 3, 0, 3, 8, 1, 4, 5, 0, 9, 2, 1 which as you can see looks pretty much like a random sequence of numbers in the range 0..9.