This is a programming quiz.  You must use Visual C++.  You may not use any notes and you may not start from a preexisting VC++ project (you must only use newly-created files in a newly-created project).

Write quickSort and radixSort in the following program.  Note that your quickSort may use any pivot selection criteria you desire.

//////////////////////////////////////////////////
/////  Sort Functions Demonstration Code
/////  by David Kosbie
//////////////////////////////////////////////////

// This program demonstrates the following 6 sorts:
// insertionSort, selectionSort, bubbleSort,
// mergeSort, quickSort, radixSort.

// The IntroCS students are responsible for the first 4
// sorts (all but quickSort and radixSort).

// The AP CS students are responsible for all 6 sorts.

//////////////////////////////////////////////////
/////  Includes, Typedefs, Constants
//////////////////////////////////////////////////

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <math.h>
#include "apvector.h"

typedef apvector<int> intVector;
typedef intVector& intVectorByReference;
typedef int& intByReference;

const int BASE = 10;
const int MAX_EXPT = 6;

//////////////////////////////////////////////////
/////  loadVector(), printVector(), and swap()
//////////////////////////////////////////////////

// loadVector() loads the vector v with
// random elements in [0,BASE^MAX_EXPT)
// (presently 10^6).
void loadVector(intVectorByReference v)
{
 // load vector with numbers mostly random in [0,BIG_NUM]
 int len = v.length();
    for (int i = 0; i < len; i++)
        v[i] = rand() % int(pow(BASE,MAX_EXPT));
}

// This function is provided here for debugging purposes,
// and is not currently called by any functions below.
void printVector(intVectorByReference v)
{
 // print vector elements separated by two spaces with
 // a carriage return at the end
    for (int i = 0; i < v.length(); i++)
        cout << v[i] << "  ";
    cout << endl;
}

void swap(intByReference x, intByReference y)
{
 int temp;
 temp = x;
 x = y;
 y = temp;
}

//////////////////////////////////////////////////
/////  insertionSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly inserts the element at the
// cursor into the sorted vector to the left of the cursor.

void insertionSort(intVectorByReference v)
{
 int len, cursor, i;
 len = v.length();
    for (cursor=1; cursor<len; cursor++)
        for (i=0;i<cursor;i++)
            if (v[i] > v[cursor])
    swap(v[i],v[cursor]);
}

//////////////////////////////////////////////////
/////  selectionSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly finds the smallest element from
// the cursor to the right end of the vector and swaps
// that element with the cursor.

void selectionSort(intVectorByReference v)
{
 int len, cursor, i;
 len = v.length();
    for (cursor=0; cursor<len-1; cursor++)
        for (i=cursor+1;i<len;i++)
            if (v[i] < v[cursor])
    swap(v[i],v[cursor]);
}

//////////////////////////////////////////////////
/////  bubbleSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly sweeps through the vector and
// swaps each pair of elements which are out of order.
// This is repeated until an entire sweep results in no swaps.

void bubbleSort(intVectorByReference v)
{
 int len, cursor;
 bool unsorted;

 len = v.length();
 unsorted = true;

 while (unsorted == true)
 {
  unsorted = false;
  for (cursor=1; cursor < len; cursor++)
   if (v[cursor] < v[cursor-1])
   {
    swap(v[cursor],v[cursor-1]);
    unsorted = true;
   }
 }
}

//////////////////////////////////////////////////
/////  mergeSort()
//////////////////////////////////////////////////

// This O(n log n) sort is much faster than the O(n^2) sorts
// above.  It is also recursive whereas the above sorts are
// iterative.  It operates by recursively sorting the left
// and right halves of the vector and then merging the sorted
// halves into a sorted whole.

void merge(intVectorByReference v,int lo,int hi)
{
 // 1. Declare variables
 int mid, mergeIndex, mergeSize, leftIndex, rightIndex;
 int leftMaxIndex, rightMaxIndex;
 bool leftHalfDone, rightHalfDone;
 intVector mergeVector;

 // 2. Initialize variables
    mid = (hi + lo) / 2;
    leftIndex = lo;
 leftMaxIndex = mid;
    rightIndex = mid+1;
 rightMaxIndex = hi;
 leftHalfDone = false;
 rightHalfDone = false;
 mergeSize = 1 + hi - lo;
 mergeVector.resize(mergeSize);

 // 3. Merge into the mergeVector
    for (mergeIndex=0; mergeIndex<mergeSize; mergeIndex++)
    {
  // Get the next element from either left half or right half,
  // place into mergeVector and advance the appropriate index.
  // Use the left half if:
  //  a)  The right side is done, or
  //  b)  The left side is not done, and the left side is smaller
        if ((rightHalfDone == true) ||
            ((leftHalfDone == false) && (v[leftIndex] < v[rightIndex])))
  {
   // Use the next element on the left half
            mergeVector[mergeIndex] = v[leftIndex];
   leftIndex++;
   if (leftIndex > leftMaxIndex)
    leftHalfDone = true;
  }
        else
  {
   // Use the next element on the right half
            mergeVector[mergeIndex] = v[rightIndex];
   rightIndex++;
   if (rightIndex > rightMaxIndex)
    rightHalfDone = true;
  }
    }

 // 4. Copy from mergeVector back into v
    for (mergeIndex=0; mergeIndex<mergeSize; mergeIndex++)
  v[lo + mergeIndex] = mergeVector[mergeIndex];
}

// This function sorts the elements from v[lo] to v[hi].
void mergeSort(intVectorByReference v,int lo,int hi)
{
 int mid;

 // 1 Base Case: if there is 1 (or fewer) elements,
 // then the vector is sorted, so just return.
    if (hi <= lo)
  return;

 // 2.  Recursive Case
    mid = (hi + lo) / 2;
    mergeSort(v,lo,mid);   // Sort the left half
    mergeSort(v,mid+1,hi); // Sort the right half
 merge(v,lo,hi);        // And merge the sorted halves
}

void mergeSort(intVectorByReference v)
{
    mergeSort(v,0,v.length()-1);
}

//////////////////////////////////////////////////
/////  quickSort()
//////////////////////////////////////////////////

// This O(n log n) sort is also recursive like mergeSort.
// It is typically about twice as fast as mergeSort.  However,
// while the average performance for quickSort is O(n log n),
// its worst-case performance (if you pick the worst pivot each
// time) is O(n^2).  Conversely, mergeSort's worst-case performance
// is the same as its average-case performance:  both are O(n log n).

// This sort operates by choosing a pivot, then splitting the
// vector so that the elements less than or equal to the pivot
// are to the left of the pivot, and those greater than the
// pivot are to the right of the pivot.  Then the two portions
// to the left and right of the pivot are recursively sorted.

void quickSort(intVectorByReference v)
{
    // YOU WRITE THIS
}

//////////////////////////////////////////////////
/////  radixSort()
//////////////////////////////////////////////////

// This sort is O(n log RANGE), where RANGE is the range of
// the elements in the vector.  For example, here we are using
// elements from 0 to 999,999, so our range is 10^6, and this
// requires 6 iterations, thus this is O(6 * n), which in fact
// is O(n).

// Thus, for large enough n, this sort will be arbitrarily
// faster than either mergeSort or quickSort (and of course
// will completely bury insertionSort, selectionSort, and bubbleSort).

typedef apvector<intVector> intVectorVector;

void radixSort(intVectorByReference v)
{
    // YOU WRITE THIS
}

//////////////////////////////////////////////////
/////  verifySorted() and testSort()
//////////////////////////////////////////////////

void verifySorted(intVectorByReference v)
{
 int cursor;
 for (cursor=v.length()-1; cursor>0; cursor--)
  if (v[cursor] < v[cursor-1])
  {
   cout << "Uh oh -- vector not sorted at index "
     << cursor << endl;
   return;
  }
 cout << "Wahoo -- the vector is sorted!" << endl;
}

// Note:  IntroCS students are *not* responsible
// for any part of the following function.
void testSortFunction(char* name,void(*sortFn)(intVector&v),intVector& v)
{
    intVector v2;
 int time1,time2;
    v2 = v;
 cout << endl << "Starting " << name << ": ";
 cout.flush();
 time1 = time(NULL);
    sortFn(v2);
 time2 = time(NULL);
 verifySorted(v2);
 cout << "Sort took: " << (time2 - time1) << " seconds" << endl;
}

//////////////////////////////////////////////////
/////  main()
//////////////////////////////////////////////////

void main()
{
    intVector v;
    int vSize;
 bool useSlowSorts;

 useSlowSorts = true;
    while (true)
    {
        cout << "Enter size of vector (0 to toggle slow sorts, <0 to exit): ";
        cin >> vSize;
        if (vSize < 0)
            return;

  if (vSize == 0)
  {
   useSlowSorts = !useSlowSorts;
   if (!useSlowSorts)
    cout << "not ";
   cout << "using slow sorts." << endl << endl;
  }
  else
  {
   v.resize(vSize);
   loadVector(v);
   cout << endl << "------------------------------";
   if (useSlowSorts)
   {
    testSortFunction("insertionSort",insertionSort,v);
    testSortFunction("selectionSort",selectionSort,v);
    testSortFunction("bubbleSort",bubbleSort,v);
   }
   testSortFunction("mergeSort",mergeSort,v);
   testSortFunction("quickSort",quickSort,v);
   testSortFunction("radixSort",radixSort,v);
   cout << "------------------------------" << endl << endl;
  }
    }
}