This is a visualization of the Median of Medians Selection Algorithm. The wikipedia entry did not do it justice for me, so I decided to create this page. The median of medians selection algorithm allows you to find the value of the ith smallest element in an array of elements in linear (O(n)) time, and constant (O(1)) extra space (the array itself still takes up linear (O(n)) space).
Okay, so how does this algorithm work? Here is some pseudocode: (We'll break it down after)
select(array, n, start, end)
if end - start <= 5
sort(array, start, end)
return array[n]
swap_index = start
for each 5 elements from start to end
sort(array, start of those 5 elements, start+4)
swap the (now) 3rd element to the swap_index-th location
swap_index = swap_index + 1
newN = start + ((swap_index - start)/2)
median = select(array, newN, start, swap_index)
location = pivot(array, median, start, end)
if(location == n)
return array[n]
else if n > newN
return select(array, n, newN+1, end)
else
return select(array, n, start, newN)
pivot(array, value, start, end)
iterate from start to end to find the appropriate location for value
iterate again moving all the elements larger than value to the right,
and all the elements less than value to the left
return value's location
Okay, now for the breakdown.
This is a recursive algorithm, so the first three lines handle the base case. The base case triggers when select is called with a range of fewer than 5 elements. The range is small enough that we can very simply return the answer without needing to make a recursive call.
The rest of the code handles the case when we call select on range of more than 5 elements.
The first five lines after the base case do a loop over the entire range of elements. For each group of five elements, it finds the median of those elements (by sorting), and then shifts those medians to the front. The medians are shifted to the front to group them together to assist with the next part.
The next two lines recursively call select to find the median those medians.
The final seven lines of select begin by using the median of medians as a pivot, putting all of the values lower than the median on one side, and all the higher values on the other. We use the median of medians as a pivot because (as we will prove in the next section) it guarantees that the pivot falls in the middle 40% of the array. If we were lucky enough to have used the nth smallest element as a pivot, we simply return that value. Otherwise, we have just divided the array into two sections, one containing only elements less than or equal to our pivot, and one containing only elements greater than or equal to our pivot, so we recursively call select on the appropriate subsection of the array.
The next part is a brief outline of the pivot function.
This pseudocode does not cover all of the corner cases, but I hope the general idea is clear.
Now that we've looked at the code, let's prove that it fits the run-time criteria we stated above.
This algorithm can be characterized by what is called a Recurrence Relation. Let's take another look at the pseudocode and focusing on the run time for each section. Our goal is to find the big O of this algorithm - O(f(n)).
The base case can be bounded by a constant number of steps, so we are just going to ignore it.
In the next section, assuming an initial array of n elements, s*n/5 operations are performed. s represents the number of operations within the for loop, and the loop is run n/5 times. Since the sorting of 5 elements can be done in fewer than some c (20 for example) operations, we say that s is O(1) time.
The third section is a recursive call to find the median of medians. There were n/5 medians so we are calling select on an array of one fifth of the original size, so f(n/5).
The final section contains a pivot and another recursive call. The pivot can be done in a single pass over the array, taking fewer than some c (10 for example) operations per element, so this term is O(n). The term for the recursive call is f(n * r) where the upper bound for r is based on the worst-case, smallest percentage of elements that we eliminate from the search space by using the median of medians as our pivot.
r is at worst 7/10ths. Why? Think about what we are eliminating when we choose the median of medians as our pivot. When we run the algorithm we end up with a group of n/5 medians, and then we choose the median of this group. This means that there are n/10 medians greater than our pivot, and n/10 medians less than our pivot. For each of these medians we have also eliminated two more elements, since each median is the middle element in a group of five. So this is three elements per median that we remove from the search space, or 3/10ths, leaving us with at most 7/10ths of the original array to search.
So combining our analysis we get f(n) = 20n/5 + f(n/5) + 10n + f(7n/10)
Now we will assume that this is linear time and attempt to solve it. If it is linear time, then f(n) = cn.
cn <= 20n/5 + cn/5 + 10n + 7cn/10
c <= 30/5 + 9c/10
c/10 <= 30/5
c <= 60
f(n) <= 60n, so f(n) is linear.
Note that if the final term had been greater than or equal to f(8n/10), the solution would not be linear because in the third step above, the left hand side would have been less than or equal to 0. Since c cannot be negative, the equation becomes unsolvable.