Quicksort and Order Statistics.

Quicksort works by choosing a random pivot and separating out the stuff before the pivot and the stuff after the pivot.  But you can use this strategy for other stuff, too.

Order Statistics:  Given an unsorted array, can you find the ith. item in sorted order...without actually sorting the array?

Q W E R T Y U I O P
0 1 2 3 4 5 6 7 8 9

You can...using something similar to QuickSort  (but not completely like QuickSort, since we won't actually be sorting anything).

Let's find the fourth element of this array.

I is our pivot.

BEF          EQ                AFT
E            I                 Q W R T Y U O P
0            0                 0 1 2 3 4 5 6 7

I don't know what the fourth element is overall, but it has be the second element of the after array.

Let's pick T as our pivot.  We no longer need the bef and eq arrays.

BEF      EQ     AFT
Q R O P  T      W Y U
0 1 2 3  4      5 6 7

We need the second element of the Before list.

O is our pivot.

BEF     EQ     AFT
        O      Q R P
        0      0 1 2

We need the first element of the after list.

R is our pivot.


BEF     EQ     AFT
Q P     R
0 1     0

We are looking for the first element in the before list.

P is our pivot.

BEF     EQ     AFT
        P      Q
        0      0

It will be the first element in the equal list.  We are done when the element in found in the equal list OR the element is found in the before or after list when that list has length one.


E I O P Q R T U W Y  <-= in sorted order, we were looking for P.


A S D F G H J K L
0 1 2 3 4 5 6 7 8

Let's find the eighth one, meaning the second one from the end, meaning it would be in position 7 if the array were sorted.

J is our pivot.

BEF        EQ    AFT
A D F G H  J     S K L
0 1 2 3 4  0     0 1 2

Looking for the second one.

So, L is our pivot.

BEF     EQ     AFT
K       L      S

Since our list is the equal list, we're done.

L is the element we seek.

This algorithm runs in Theta(n) expected time, but Theta (n^2) worst case time.

WE CAN DO BETTER!  We can get it to run in Theta(n) worst-case time, by making sure we never pick a bad pivot.


The way to do this is with the median-of-medians approach.

1.  Break array into groups of 5.  (The last group might have fewer than 5).

2.  Find the median of each group of 5, using brute force.  (I just sort them and grab the middle.)

3.  Take all of these medians and find the median of these medians using this very same order statistic algorithm; use "(len+1)/2" to specifiy with element you're looking for.

4.  This median of medians is the pivot.  Split the original list into before, eq, and after lists around this pivot.  If the element you're looking for is in the equal list OR it's in a before or after list of length one, you're done.  Otherwise, call this very same order statistic algorithm on either the before or after list, whichever is appropriate.