The median of a list of elements.

The median is the element that is in the middle (there are an equal number of elements larger and smaller than the given element.

(1,3,7,6,0):  what is the median?  3

How would you write a program to find the median?  Sort the list and look at the middle element.  Theta (n lg n) time.

You can do this in Theta (n) time.

We generalize this to be the "Linear-Time Selection Algorithm".  Given an unsorted an array, can you grab what would be the kth. element if the list were sorted, and can you do it in Theta(n) time?  (i.e. without actually sorting the array.)

Think of the quicksort.

Let's digress and talk about the QuickSort.

QuickSort expects to run in Theta (n lg n) time.  But it might run in worse.

If you choose the smallest in the array to be the pivot, then the bef is of size 0 and eq list is of size 1, and the after list is size n-1.

If you again choose the smallest, you have an after list of size n-2, and so on.

If you choose a bad pivot EVERY SINGLE TIME, QuickSort runs in Theta (n^2) time.

I used separate bef, eq, and aft lists.  Most people do not do this.  Most people move data around in the arrays because this takes less storage space (which is a good thing).

A stable sort is one that preserve the relative order of elements in the event of a tie.

4 9 8 5 5

4: I
9: DONT
8: LIKE
5: ICE
5: CREAM

4 5 5 8 9

4: I
5: ICE
5: CREAM
8: LIKE
9: DONT

The 5's are in the same order they were in the original list.  If this is guaranteed to be the case, that's a stable sort.