0. Note:  This is an ungraded assignment.  Part A includes code to review for the quiz on Monday Dec-4, and Part B includes a description of the debugging techniques which may appear on a pop quiz sometime later this week.

//////////////////////////////////////////////////
/////  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.

int getPivotIndex(intVectorByReference v,int lo,int hi)
{
 return lo;
}

int pivot(intVectorByReference v, int lo, int hi)
{
 int pivotIndex;
 // 1. get a pivot index and swap it to the first position
 pivotIndex = getPivotIndex(v,lo,hi);
 swap(v[pivotIndex],v[lo]);

 // 2. Swap elements as necessary so those less than or
 //    equal to the pivot are in the left portion, and
 //    those greater than the pivot are in the right portion
 //    of the vector.
 int loPointer = lo + 1; // lo is the pivot, and we don't count it
 int hiPointer = hi;

 while (loPointer < hiPointer)
 {
  if (v[loPointer] <= v[lo])
   loPointer++;
  else if (v[hiPointer] > v[lo])
   hiPointer--;
  else
   // Both left and right elements are on the wrong
   // side, so swap them and continue.
   swap(v[loPointer],v[hiPointer]);
 }

 // 3. Swap the pivot into the new location
 assert(loPointer == hiPointer);
 int newPivotIndex;
 if (v[loPointer] <= v[lo])
  newPivotIndex=loPointer;
 else
  newPivotIndex=loPointer-1;
 swap(v[newPivotIndex],v[lo]);
 return newPivotIndex;
}

void quickSort(intVectorByReference v,int lo, int hi)
{
 if (lo >= hi)
  return;

 int p = pivot(v,lo,hi);

 quickSort(v,lo,p-1);
 quickSort(v,p+1,hi);
}

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

//////////////////////////////////////////////////
/////  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)
{
 intVectorVector buckets(BASE);
 intVector bucketCount(BASE);
 int i, len, bucket, bucketSize;
 len = v.length();

 // Initialize buckets
 int defaultBucketSize = 10 + 2 * len / BASE;
 for (i=0;i<BASE;i++)
 {
  bucketCount[i] = 0;
  buckets[i].resize(defaultBucketSize);
 }

 // Iterate over each expt up to MAX_EXPT
 int divver, modder = 1;
 for (int expt=0; expt < MAX_EXPT; expt++)
 {
  modder *= BASE;
  divver = modder / BASE;
  // 1.  Place each element v[j] into the approprate bucket
  //     based on the expt'th digit in v[j]
  for (int j=0;j<len;j++)
  {
   bucket = (v[j] % modder) / divver;
   bucketSize = buckets[bucket].length();
   // add v[j] to this bucket now
   // first make sure there is room
   if (bucketCount[bucket] >= bucketSize)
    buckets[bucket].resize(2*bucketSize);
   buckets[bucket][bucketCount[bucket]] = v[j];
   (bucketCount[bucket])++;
  }

  // 2.  Copy the buckets, from bucket[0] to bucket[BASE-1],
  //     back into v.
  //     AND clear the buckets for the next iteration by
  //     resetting the bucket count to 0!
  int vIndex = 0;
  for (bucket = 0; bucket < BASE; bucket++)
  {
   for (i=0; i<bucketCount[bucket];i++)
    v[vIndex++] = buckets[bucket][i];
   bucketCount[bucket] = 0;
  }
 }
}

//////////////////////////////////////////////////
/////  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;
  }
    }
}

Your assignment:  learn how to use the debugger.  Do this by stepping through code you have already written.  Intro CS students are responsible for the following (and yes, you must know these by their F-keys (meaning, you must simply know what Shift-F11 does, for example), and yes, you may be quizzed on this as soon as tomorrow):

• Variables window (how to view and *set* Auto and Locals)
• Watch window (for example, how to evaluate v.length() in the debugger)
• Call Stack window (how to move up and down the call stack)
• How to start a program or continue running from a user breakpoint (F5)
• How to set and clear breakpoints (F9)
• How to step into (F11), and why you would do so
• How to step over (F10), and why you would do so
• How to step out of (Shift-F11), and why you would do so
• How to run to cursor (Ctrl-F10), and why you would do so
• How to set next statement (rightclick on statement), and why you would do so

• Boundary case analysis (which inputs you should test your program on)
• Commenting out working code to home in on the bug
• Using assert statements

Carpe diem.

DK