CS 202 Fall 2013
In-Class Challenge for Thursday, December 12, 2013

Our Goal

We wish to write a recursive function template quicksort that does Quicksort.

Prototype quicksort as follows.

[C++]

template <typename Iter>
bool quicksort(Iter first, Iter last);

The function is given a range specified by two random-access iterators: first and last, in the usual way. It might be called as follows.

[C++]

vector<int> v;

quicksort(v.begin(), v.end());

Some (Hopefully) Helpful Things

Quicksort

Find the size of the given range. This is last - first. Save this in a variable.

You will need a base case: when size < 1.

Then comes the recursive case. Choose a pivot (the first item in the range) and make an iterator to it. Then call partition. Lastly, make two recursive calls: sort first half, sort second half.

Skeleton File

I have provided an unfinished version of header quicksort.h. You may wish to start your work with it, to save time.

What to Do

1. Write function template quicksort, in header quicksort.h. Since this is a template, there is no associated source file. The resulting code should compile and pass all tests in the given test program: test_quicksort.cpp.