0.  Reminders

a)  There is a full-fledged quiz (not a mini-quiz) tomorrow on Assignments 16-21 (Monte Carlo methods, Classes, and Algorithms)
b)  You do not have to demonstrate progress on this assignment by tomorrow.
c)  One more search routine was added to this assignment -- bubbleSort (it's in the book).
d)  A very easy graphing problem was also added to this assignment.
e)  There is a quiz on Tuesday of next week on the material in this assignment.

2.  Write the 6 missing functions in the code below (after the instructions).

3.  Plot a graph of each function, mapping execution time against size of the vector.  Yes, you must turn in 4 separate plots -- one each for selectionSort, insertionSort, bubbleSort, and mergeSort.

4. Heads up on where we are headed:  next week, you will learn quickSort, treeSort, heapSort, and radixSort.  Wahoo!  More seriously, time permitting, you may wish to read about these in the book this week, thus giving you a bit more free time over the Thanksgiving holiday.

5.  Good luck, and have a grand weekend.

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

const int BIG_NUM = 500;

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

// loadVector() loads the vector v with
// random elements between 0 and BIG_NUM

void loadVector(intVectorByReference v)
{
 // load vector with numbers mostly random in [0,BIG_NUM]
// YOU WRITE THIS, PART 1 of 6
}
 

void printVector(intVectorByReference v)
{
 // print vector elements separated by two spaces with
 // a carriage return at the end
// YOU WRITE THIS, PART 2 of 6
}

void insertionSort(intVector& v)
{
// YOU WRITE THIS, PART 3 of 6
}

void selectionSort(intVector& v)
{
// YOU WRITE THIS, PART 4 of 6
}

void bubbleSort(intVector& v)
{
// YOU WRITE THIS, PART 5 of 6
}

void mergeSort(intVector& v,int lo,int hi)
{
// YOU WRITE THIS, PART 6 of 6
}

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

void testSortFunction(char* name,void(*sortFn)(intVector&v),intVector& v)
{
    intVector v2;
 int time1,time2;
    v2 = v;
 cout << "Starting " << name << endl;
 time1 = time(NULL);
    sortFn(v2);
 time2 = time(NULL);
 cout << "Sort took: " << (time2 - time1) << " seconds" << endl;
}

void main()
{
    intVector v;
    int vSize;

    while (true)
    {
        cout << "Enter size of vector (<0 to exit): ";
        cin >> vSize;
        if (vSize < 0)
            return;
        v.resize(vSize);
        loadVector(v);
        // printVector(v);
        testSortFunction("selectionSort",selectionSort,v);
        testSortFunction("insertionSort",insertionSort,v);
        testSortFunction("bubbleSort",bubbleSort,v);
        testSortFunction("mergeSort",mergeSort,v);
    }
}