This assignment  is due on Tuesday Oct-17.  We will have a quiz on Wed Oct-18 covering all material up to and including this assignment.  Finally, there will be an optional review period after school on Tuesday.

Also note:  for those who had problems with Assignment 12 (already due), there will be an optional review session on that, and probably some of this material as well, during P1 Rotation on Monday.

Step 0:  Overview
In this assignment, you will learn to sort an array.  We will do this using the most basic (and least efficient!) sorting algorithm.  It is called selection sort.  This works in the simplest fashion, progressively sorting the array by selecting the smallest remaining element and filling the array left-to-right:

• Find the smallest element (starting from the 0th element)
• Swap it with the 0th element.
• Find the smallest element (starting from the 1st element)
• Swap it with the first element.
• ...

int findMaxValue(apvector<int>& v)
{
    int i, max;
    max = v[0];
    i = 0;
    while (i < SIZE)
    {
        if (v[i] > max)
        {
            max = v[i];
        }
        i = i + 1;
    }
    return max;
}

Step 2:  How to write a Function which returns an Index
This is very straightforward, but worth noting explicitly.  Sometimes it is better to return the index rather than the value stored in that index.  It is best to modify the function name accordingly.  Contrast the following function with the previous example (new or modified lines are in bold):

int findIndexOfMaxValue(apvector<int>& v)
{
    int i, max, maxIndex;
    max = v[0];
    maxIndex = 0;
    i = 0;
    while (i < SIZE)
    {
        if (v[i] > max)
        {
            max = v[i];
           maxIndex = i;
        }
        i = i + 1;
    }
    return maxIndex;
}

int findIndexOfSmallestRemainingValue(apvector<int>& v, int startIndex)
{
    // This function returns the index of the smallest value in the
    // vector v starting at index startIndex up to index SIZE-1.
    // So, it finds the smallest of v[startIndex], v[startIndex+1],
    // ..., v[SIZE-1].
}

void swapValues(apvector<int>& v, int index1, int index2)
{
    // This function swaps the values stored in v[index1]
    // and v[index2].  Recall that you will need to
    // use a temporary value to do this correctly.
}

Step 5:  Write the function sortVector (done for you):
This function uses the functions described above, and works as such (it is written in its entirety here):

void sortVector(apvector<int>& v)
{
    int i, smallestIndex;

    i = 0;
    while (i < SIZE)
    {
        smallestIndex = findIndexOfSmallestRemainingValue(v,i);
        swapValues(v,i,smallestIndex);
        i = i + 1;
    }
}

void loadVector(apvector<int>& v)
{
    // This function loads the vector v of size SIZE with values
    // read in from the user.  This is essentially already written
    // from your previous assignment.
}

void printVector(apvector<int>& v)
{
    // This function prints all the values in the vector v
    // of size SIZE using cout's. This is also essentially
    // already written from your previous assignment.
}

void main()
{
    apvector<int> v(SIZE);
    loadVector(v);
    sortVector(v);
    printVector(v);
    getchar();
}

Step 10:  Overview regarding Time Of Execution

InsertionSort can sort a list with N elements in it in "quadratic" time.  For now, suffice it to say that this has two implications which we are going to empirically confirm here:

1.  Doubling the size of the list (N) should increase the run time by 4 times.
2.  A graph of run time versus size-of-list should be a parabola.

Step 11:  Converting main() for timing purposes (done for you)
In order to time executions, we need to run the program many times repeatedly.  We also need to eliminate any printing, since that is extremely slow.  To accomplish the first part -- running repeatedly, we will use a second vector, vTemp, and we will repeatedly copy vTemp into v, then sort v.  For the second part, we will just omit the printVector() call.  Here is the resulting main(), along with the copyVector() function we need:

void copyVector(apvector<int>& targetVector, apvector<int>& sourceVector)
{
    int i;
    i = 0;
    while (i < SIZE)
    {
        targetVector[i] = sourceVector[i];
        i = i + 1;
    }
}

const int SIZE = 10;
const int MAX_ITERATIONS = 10000;

void main()
{
    apvector<int> v(SIZE);
    apvector<int> vTemp(SIZE);
    int iterations;

    loadVector(v);
    iterations = 0;

    cout << "Hit Enter when ready with stopwatch... " << endl;
    getchar();

    while (iterations < MAX_ITERATIONS)
    {
        copyVector(vTemp,v);
        sortVector(vTemp);
        iterations = iterations + 1;
    }

    // printVector(v);

    cout << "Done -- stop the stopwatch!" << endl;
    getchar();
}

Step 13:  Measuring Runtimes for Various SIZE's:
Now you should run the code with SIZE equal to 5, 10, 15, and 20.  For each size, very carefully time the execution with a stopwatch.  Call this function ExecutionTime(size).

Step 14:  Graph Your Results:
Here we finally confirm the assertions in Step 10.  First, we said that every time you double the size, the runtime should grow by a factor of 4.  Confirm this by computing ExecutionTime(10) / ExecutionTime(5), and also ExecutionTime(20) / ExecutionTime(10), and noting (hopefully) that these ratios are very close to 4.  Next -- and finally -- plot a graph (yes, on real graph paper (though you could also use Excel's charting, if you prefer)) with size as the x-axis, and ExecutionTime(x) as the y-axis.  You should have 5 points:  one each at x=0,5,10,15,20 (note that y=0 when x=0, since of course it takes no time to sort an empty list!).  If all went well, your graph should look like a beautiful parabola.  Does it?!?

Step 15:  What to submit?
Turn in your graph, your answers to the other two questions in Step 14, and a printout of your code.  Be sure it is all stapled together and properly labeled with your name and "Assignment 13".

Have a most autumnal weekend.

DK