From selection to sorting

When I first saw the quicksort it was in an algorithms class back in the day. We first learned the quicksort, then choosing a good pivot element and then as an afterthought we did quickselect.

Fast forward to teaching. I was never really happy teaching quicksort. Mergesort is easy to motivate and it's pretty easy to write. Quicksort always felt a little forced.

I thought I'd try switching things up this time and doing quickselect first.

The motivating problem: find the K^th smallest item in a list - in our case the list is an array of ints.

I want to start with the least efficient algorithm so I stack the deck. I remind them that we've been finding the smallest item in a list for two years now.

They don't disappoint and suggest something like this:

L = [10,3,28,82,14,42,66,74,81]

def findKth(L,k):
    omits=[]
    for i in range(k):
        ans=max(L)
        for item in L:
            if item < ans and item not in omits:
                ans=item
        omits.append(ans)
    return ans

print findKth(L,3)

Clearly an \(O(n^2)\) algorithm.

Can we do better?

Certainly.

The students then suggest sorting the data set first. If we use mergesort, we can sort in \(O(nLg (n))\) time. This lead to a great conversation about sorting being so fast it's practically free and that you don't have to hard code everything from scratch. Not only is sorting the data set then plucking the k^th item out much faster, if you already have a sort written or if you use your language's library's sort, it's much easier as well:

def findKth(L,k):
    tmp = sorted(L)
    return tmp[k]

But we can do even better. So now we talk about quickselect

We pick a random pivot, partition the list a la quicksort (reorder the list such that all items less than the pivot are to its left, and all items greater than the pivot are to its right).

We now know that after partitioning. the pivot is in it's exact location. If its index is k then we're done. If not, we can recursively quickselect on either the left or right side.

Pretty cool, but is it faster?

It's easy to see that if we keep choosing a bad pivot (the smallest or largest in the list), each iteration takes \(n\) time to partition and each iteration takes one item out of contention. This takes us back to \(O(n^2)\).

However…

If we choose a good partition – at the middle of the list, each partition takes less and less time. We get a run time of:

\(n+\frac{n}{2} +\frac{n}{4}+\frac{n}{8}+\dots\) and since \(\frac{n}{2} +\frac{n}{4}+\frac{n}{8}\dots=n\) this becomes an \(O(2n)\), or \(O(n)\) algorithm.

That's really cool.

Homework was the actual implementation.

I think this might be a better way to approach quicksort. It seems less forced, plus the class gets to go through the exercise of taking an algorithm form \(O(n^2)\) to \(O(nlg(n))\) to \(O(n)\).

Next, moving to the quicksort and also showing that we can indeed avoid those really bad pivots.

Addendum