Section 3 - Arrays, Methods and Sorting

8A.3.1 Passing Arrays to Methods

Unlike most variables passed normally into functions, if you pass an array into a method as a parameter, any changes made to the array elements will persist after the method returns.  This is good if you want the method to modify the array, and bad if you don't.

Let's take advantage of this in a method that will "float" the largest element of a double array to the top of the array.

Here is our desired output:

  console shot

Notice that the 199.9 ended up in the last position on the right, as we desired.  Also, the array was modified in other places, as well, but that isn't as important to us.

We have two methods for this program.  Since we are not using OOP right now, we will make them both ordinary functions and call them from main() without any object  dereference.  One method will float the largest element of the array to the top. The other method will print out the array for us. 

Note that we pass the printArray() method three arguments: 

  1. the string to place on the title ("Before: " or "After: ")
  2. the array to print
  3. the size of the array

This last item is essential.  C++ does not know how large the size of the passed-in array is.

Also notice the syntax of the formal parameter list in a method that takes an array:

void func( double arrayParam[] )

Of course, double could be any primitive type or class name, and represents the basic type of the array.

floatLargestToTop() returns a bool true if a change was made to the array, and false if not.  We are not going to make use of this return type in our main() just yet.

#include <string>
#include <iostream>
using namespace std;

// method prototypes
bool floatLargestToTop(double data[], int arraySize);
void printArray(string title, double data[], int arraySize);

int main ()
{
double myArray[] = {10.2, 56.9, -33, 12, 0, 2, 4.8, 199.9, 73, -91.2};

// compute the size of the array
short arraySize = sizeof(myArray)/sizeof(myArray[0]);

printArray("Before: ", myArray, arraySize);
floatLargestToTop(myArray, arraySize);
printArray("After: ", myArray, arraySize);
}

// returns true if a modification was made to the array
bool floatLargestToTop(double data[], int arraySize)
{
bool changed = false;
double temp;

// notice we stop at arraySize-2 because of expr. k+1 in loop
for (int k = 0; k < arraySize-1; k++)
if (data[k] > data[k+1])
{
temp = data[k];
data[k] = data[k+1];
data[k+1] = temp;
changed = true;
}
return changed;
}

// print out the array with the string as a title for the message box
void printArray(string title, double data[], int arraySize)
{
cout << title << "  ";

for (int k = 0; k < arraySize; k++)
{
cout << data[k] << "   ";
// every fifth element, print newline
if (k % 5 == 4)
cout << endl;
}
cout << endl;
}

Study the for loop inside the floatLargestToTop() method and make sure you understand what's going on.  It simply compares adjacent elements in the array and swaps them if the left one is larger than the right.  It does this starting at the bottom of the array and moving to the top, thereby moving the large elements gradually to the right.  Besides moving the largest to the top, it also helps move some of the other large elements more to the right (higher), and other small elements, more to the left (lower).

8A.3.2 Sorting

If you followed the relatively simple concept of the method floatLargestToTop() then you have actually comprehended a much more sophisticated and universal concept for free:  sorting.  Sorting, the technique (algorithm) for placing arrays in increasing or decreasing order, has long been a topic of computer science classes, and is actually studied in graduate courses.  And you are only one statement away from understanding sorting.  Here's the statement:

for (int k = 0; k < arraySize; k++)

"That's just a for loop control," you say?  Right.  What I'm telling you is that if you add this one statement to your main() method, you will have sorted the initial array so that it will appear  in increasing order.  Here's what I mean.  We repeat the method call to floatLargestToTop() exactly arraySize times, and you will end up with a sorted array.

printArray("Before: ", myArray, arraySize);
for (int k = 0; k < arraySize; k++)
floatLargestToTop(myArray, arraySize);
printArray("After: ", myArray, arraySize);

If you make this change and run the program, you will get this result:

console shot

Nice, eh? What happened? Each time we called the method, a new number got floated as far to the top as it could.  That is, once the largest number was placed at the end of the list, it did not interfere with the second largest making it almost to the end.  Then that number didn't interfere with the third largest making its way to the third-from-top spot, etc.

Before doing anything else, we have to modularize this so that it is contained in a method of its own, arraySort():

void arraySort(double array[], int arraySize)
{
for (int k = 0; k < arraySize; k++)
floatLargestToTop(array, arraySize);
}

This important step removes from main() the responsibility of having the sorting algorithm partly in it, and partly in the floatLargestToTop() method.  We always want to encapsulate a reusable task in a method of its own.  Once we do this, main() looks (once again)  simple:

printArray("Before: ", myArray, arraySize);
arraySort(myArray, arraySize);
printArray("After: ", myArray, arraySize);

And there you have a fully functional arraySort() method that is extremely short.

8A.3.3 Improving the Sort Algorithm

We can make this algorithm smarter.  For one, what do we know if we called floatLargestToTop() and no modifications were made to the array?  We would know that the array is done being sorted.  This often happens after only a few calls to floatLargestToTop() since each call improves the situation quite a bit.  So our first improvement is to use the bool return value that we have been ignoring up to now:

void arraySort(double array[], int arraySize)
{
for (int k = 0; k < arraySize; k++)
if ( !floatLargestToTop(array, arraySize-1-k) )
return;
}

The next improvement involves the realization that each time we call floatLargestToTop(), we can stop a little closer to the beginning of the array.  That is, the loop inside floatLargestToTop() can get shorter every time we call it.  For this, we need a second parameter to that method that tells it how far to go.

Finally, there is a little swap operation that is screaming out to be in a method of its own.  So we do that as well.

Here are all the methods that, together, make up the array sort with this change:

// returns true if a modification was made to the array
bool floatLargestToTop(double data[], int top)
{
bool changed = false;

// notice we stop at length -2 because of expr. k+1 in loop
for (int k =0; k < top; k++)
if (data[k] > data[k+1])
{
changed = true;
mySwap(data[k], data[k+1]);
}
return changed;
}
void arraySort(double array[], int arraySize)
{
int everShrinkingTop;

for (   everShrinkingTop = arraySize - 1;
everShrinkingTop > 0;
everShrinkingTop--
)
if ( !floatLargestToTop(array, everShrinkingTop) )
return;
}
void mySwap(double &a, double &b)
{
double temp;

temp = a;
a = b;
b = temp;
}

Notice that the mySwap() method uses reference parameters because we have to change the values of the two parameters and have those changes reflected back in the client.