Section 4 - Review of Sorting

2B.4.1 Sorting an Array of Strings

In order to make the binary search algorithm work we have to sort the array of Students in alphabetical ordering.  You should have had sorting in CS 2A. If so, you can skip this section.  If you want the review, here is a separate example that shows how to sort an array.  In this case we are sorting based on name so we use the string compare() function:

string1.compare( string2 )

If we were sorting on a numeric key, we would use <  as the comparison.

The output would look like this:

Here is the program that demonstrates an arraySort() method and some other methods that it calls.  As with all methods that take an array as a parameter, we pass the size of the array as a separate parameter so the method knows how large the array is..

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

// method prototypes
bool floatLargestToTop(string data[], int arraySize);
void printArray(string title, string data[], int arraySize);
void arraySort(string array[], int arraySize);
void swap(string &a, string &b);

int main ()
{
  string myArray[] = {"you", "me", "them", "us", "him",
  "her", "he", "she"};

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

  printArray("Before: ", myArray, arraySize);
  arraySort(myArray, arraySize);
  printArray("After: ", myArray, arraySize);
}
// returns true if a modification was made to the array
bool floatLargestToTop(string 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].compare(data[k+1]) > 0)
    {
      swap(data[k], data[k+1]);
      changed = true;
    }
  return changed;
}

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

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

}
void arraySort(string array[], int arraySize)
{
  for (int k = 0; k < arraySize; k++)
    if (!floatLargestToTop(array, arraySize-1-k))
      return;
}
void swap(string &a, string &b)
{
  string temp;

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