0.  You may discuss the "discussion" portions of this assignment with others, but as for the programming portions, those you must work alone on (no exceptions).  Also, due to P1 rotation on Monday, this assignment is due Tuesday.  Finally, be sure to read the whole assignment first -- there is not much programming in this assignment, but a fair bit of reading and (oh no!) thinking.  Good luck!

A1.  Discussion of By-Reference:  addOne()

Consider the following code:

#include <stdio.h>
#include <iostream.h>

void addOne(int y)
{
 y = y + 1;
}

void main()
{
 int x;
 x = 1;
 addOne(x);
 if (x == 2)
 {
  cout << "It added one (yippee!!!)" << endl;
 }
 else
 {
  cout << "It did not add one (wimper).." << endl;
 }
 getchar();
}

• Surely addOne() does add one to y (right?).
• But...  The variable "y" in addOne() is not the same variable as the variable "x" in main().
• When main() calls addOne(), x is copied into y.  Sure, y is changed, but this is just a copy of x.  The real x in main() is left unchanged.

#include <stdio.h>
#include <iostream.h>

void addOne(int x)
{
 x = x + 1;
}

void main()
{
 int x;
 x = 1;
 addOne(x);
 if (x == 2)
 {
  cout << "It added one (wahoo!!!)" << endl;
 }
 else
 {
  cout << "It did not add one (wimper).." << endl;
 }
 getchar();
}

So what to do?  What we are seeking is a way that a function can directly modify the variable provided, rather than simply get a copy of that variable.  And it turns out we can do just that....

Introducing:  By-Reference Parameters (applause...).  This does precisely what we want.  If we modify addOne() so that it's parameter is intByReference, rather than just an int, then any changes it makes to the parameter will directly modify the variable provided to the function.  That is, addOne() will actually change "x" in main().

One oddity:  to do this, we need to include a "magic" line in our code:  typedef int& intByReference.  We will discuss this line in detail later, but for now please take a leap of faith and just include it in your code (many thanks).

So, here is the resulting code (modifications in red):

#include <stdio.h>
#include <iostream.h>

typedef int& intByReference;

void addOne(intByReference y)
{
 y = y + 1;
}

void main()
{
 int x;
 x = 1;
 addOne(x);
 if (x == 2)
 {
  cout << "It added one (zowie!!!)" << endl;
 }
 else
 {
  cout << "It did not add one (wimper).." << endl;
 }
 getchar();
}

A2.  More Discussion of By-Reference:  swap()

The previous example was less-than-inspiring because addOne() is basically useless.  So here we move on to a genuinely interesting and useful function:  swap().  This function takes two integers and, well, swaps them.  Thus, if x is 1 and y is 2 and we call swap(x,y), afterwards we expect x to be 2 and y to be 1.  By now you appreciate that such a function is definitely useful, since swapping is a very common programming activity.  Well, let's have a go at it...

Consider the following code:

#include <stdio.h>
#include <iostream.h>

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

void main()
{
 int x, y;
 x = 1;
 y = 2;
 swap(x,y);
 if (x == 2)
 {
  cout << "x and y were swapped (hurray!!!)" << endl;
 }
 else
 {
  cout << "alas and alack, the swap failed (woe is me).." << endl;
 }
 getchar();
}

• the "x" and "y" in swap() are only copies of the "x" and "y" in main().
• So swapping them had no effect on the originals.  Bummer.

• Declare the "x" and "y" in swap() to be by reference
• Thus, changes to them will actually change the originals.

#include <stdio.h>
#include <iostream.h>

typedef int& intByReference;

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

void main()
{
 int x, y;
 x = 1;
 y = 2;
 swap(x,y);
 if (x == 2)
 {
  cout << "x and y were swapped (hot diggety dog!!!)" << endl;
 }
 else
 {
  cout << "alas and alack, the swap failed (wimper).." << endl;
 }
 getchar();
}

One last comment:  if parameters are not "by-reference" -- that is, if they are plain old parameters like we've been using until this point in the class -- then we say they are "by-value" (meaning that you get a copy of the value of the variable, as opposed to the actual variable).  Thus, you are now experts on By-Reference versus By-Value.  Congratulations.

A3.  More Discussion of By-Reference:  addOneToVectorElements()

Now we turn the topic to vectors.  Let's say we wanted write addOneToVectorElements(), which would, curiously enough, add one to each element in a vector.  Consider the following code (to run this, of course, you will have to place apvector.cpp and apvector.h in the project directory, and add apvector.h to your project):

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

typedef apvector<int> intVector;

void addOneToVectorElements(intVector v)
{
 int i, len;
 len = v.length();
 i = 0;
 while (i < len)
 {
  v[i] = v[i] + 1;
  i = i + 1;
 }
}

void main()
{
 intVector v;
 v.resize(2);
 v[0] = 1;
 v[1] = 2;
 addOneToVectorElements(v);
 if ((v[0] == 2) && (v[1] == 3))
 {
  cout << "the vector elements were increased by one (whoopee!!!)" << endl;
 }
 else
 {
  cout << "Ixnay (wimper).." << endl;
 }
 getchar();
}

Note:  To do this, we need to add another "magic" line of code:  typedef intVector& intVectorByReference.  Deal with it.

So here then is the resulting code:

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

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

void addOneToVectorElements(intVectorByReference v)
{
 int i, len;
 len = v.length();
 i = 0;
 while (i<len)
 {
  v[i] = v[i] + 1;
  i = i + 1;
 }
}

void main()
{
 intVector v;
 v.resize(2);
 v[0] = 1;
 v[1] = 2;
 addOneToVectorElements(v);
 if ((v[0] == 2) && (v[1] == 3))
 {
  cout << "the vector elements were increased by one (yahoooeee!!!)" << endl;
 }
 else
 {
  cout << "Ixnay (wimper).." << endl;
 }
 getchar();
}

A4.  More Discussion of By-Reference:  loadVectorWithRandomElements()

Of course, addOneToVectorElements() is, well, lame.  Ok, pathetically useless.  Let's do something more useful.  Here, we will write a function which loads a vector with random elements.  Consider the following code fragment:

void loadVectorWithRandomElements(intVector v)
{
 int i,len;
 len = v.length();
 i = 0;
 while (i < len)
 {
  v[i] = rand();
  i = i + 1;
 }
}

void loadVectorWithRandomElements(intVectorByReference v)
{
 int i,len;
 len = v.length();
 i = 0;
 while (i < len)
 {
  v[i] = rand();
  i = i + 1;
 }
}

A5.  Last Discussion of By-Reference:  findAverage() and Efficiency

Lastly, consider writing a function called findAverage() which takes a vector as input and which returns the average value of the elements in the vector.  Consider the following code:

int findAverage(intVector v)
{
 int result, sum, i, len;
 sum = 0;
 i = 0;
 len = v.length();
 while (i < len)
 {
  sum = sum + v[i];
  i = i + 1;
 }
 result = sum / len;
 return result;
}

Thus, for efficiency, we want to avoid copying and thus we change "v" to be by reference, as follows:

int findAverage(intVectorByReference v)
{
 int result, sum, i, len;
 sum = 0;
 i = 0;
 len = v.length();
 while (i < len)
 {
  sum = sum + v[i];
  i = i + 1;
 }
 result = sum / len;
 return result;
}

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

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

void loadVectorWithRandomElements(intVectorByReference v)
{
 int i,len;
 len = v.length();
 i = 0;
 while (i < len)
 {
  v[i] = rand();
  i = i + 1;
 }
}

int findAverage(intVectorByReference v)
{
 int result, sum, i, len;
 sum = 0;
 i = 0;
 len = v.length();
 while (i < len)
 {
  sum = sum + v[i];
  i = i + 1;
 }
 result = sum / len;
 return result;
}

void main()
{
 intVector v;
 int len;
 cout << "Enter the length of the vector: ";
 cin >> len;
 v.resize(len);
 loadVectorWithRandomElements(v);
 cout << "The average of the random elements: "
      << findAverage(v) << endl;
 getchar();
}

A6.  By Reference Redux

The last word:  As you no doubt already guessed, this material will appear on a quiz or two next week.

B1.  Discussion of SelectionSort:

As we have previously discussed, there are many algorithms for sorting.  One sorting algorithm is called SelectionSort.  We will investigate it here.  This is how SelectionSort works:

• SelectionSort:  moving a cursor from left to right through the vector, find the smallest remaining element from the cursor to the end of the vector and swap that element with the element at the cursor.

87  54  29  18  94  73  12  63

cursor: 87  54  29  18  94  73  12  63

cursor: 87  54  29  18  94  73  12  63

cursor: 12  54  29  18  94  73  87  63

12  cursor:  54  29  18  94  73  87  63

12  cursor:  54  29  18  94  73  87  63

12  cursor:18  29  54  94  73  87  63

12  18  cursor:   29  54  94  73  87  63

Because of this:  once the cursor moves to the right end of the vector, the entire vector is sorted.

This is the logic behind SelectionSort.  It is called "SelectionSort" because at each step we select the next smallest element in the vector.  Et voila.

B2.  More Discussion of SelectionSort:

Here is the code for SelectionSort:

void selectionSort(intVectorByReference v)
{
 int cursor,i,len,smallestIndex,temp;
 len = v.length();
 cursor = 0;
 while (cursor < len-1)
 {
  // 1.  Find the index of the smallest
  //     element in the vector starting
  //     at v[cursor] to the end of the vector.
  smallestIndex = cursor;
  i = cursor+1;
  while (i < len)
  {
   if (v[i] < v[smallestIndex])
   {
    smallestIndex = i;
   }
   i = i + 1;
  }

  // 2.  Now that we have the index of the
  //     smallest remaining element, swap
  //     that element with v[cursor].  Thus, after
  //     this step, the elements v[0], v[1],
  //     ..,v[cursor] will be the (cursor+1) smallest
  //     elements in the vector, in order.
  temp = v[cursor];
  v[cursor] = v[smallestIndex];
  v[smallestIndex] = temp;

  // 3.  Increment cursor to continue
  cursor = cursor + 1;
 }
}

B3.  End of Discussion

To be clear, this ends the discussion part of this assignment.  All that follows is the programming portions, and you must work alone on the remaining portions.

B4.  Change the function loadVectorWithRandomElements() from above so that the random numbers are in the range [0,99] rather than [0,RAND_MAX].

B5.  Write a function printVector() which takes a vector as its only parameter and prints the vector.  If there are more than 30 elements in the vector, your function should just print the first 15 elements, then an ellipsis (3 dots), then the last 15 elements.

• Note that, for efficiency, the vector parameter should be by reference.
• Also note that 30 is a "magic number" and so should be a constant.  To do that, add a line above your function of the form:  const int MAX_ELEMENTS_TO_PRINT = 30;
• Also, 15 is magic, and should be MAX_ELEMENTS_TO_PRINT/2
• Here is some sample output -- be sure to exactly match this output:

(Though here I set MAX_ELEMENTS_TO_PRINT to 6 to save space):

v[0] = 41
v[1] = 32
v[2] = 340
...
v[8] = 3720
v[9] = 4020
v[10] = 4130

B7.  Here is the shell of the program which you should submit.  When you are done, it must contain the functions which you wrote for parts B4, B5, and B6 -- that is, loadVectorWithRandomElements(), printVector(), and selectionSort().

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

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

const int MAX_ELEMENTS_TO_PRINT = 6;

void printVector(intVectorByReference v)
{
 // YOU WRITE THIS, PART 1 of 3
}

void selectionSort(intVectorByReference v)
{
 // YOU WRITE THIS, PART 2 of 3
 // (be sure it sorts largest-to-smallest)
}

void loadVectorWithRandomElements(intVectorByReference v)
{
 // YOU WRITE THIS, PART 3 of 3
}

void main()
{
 intVector v;
 int len;
 cout << "Enter the length of the vector: ";
 cin >> len;
 v.resize(len);
 loadVectorWithRandomElements(v);
 printVector(v);
 getchar();
 selectionSort(v);
 printVector(v);
 getchar();
}

See Course Home Page.