LAB 5 -- Sorting arrays

In this lab you will learn Quicksort, one of the fastest known algorithms for sorting an array in-place, and Binary Search, the method for searching in a sorted array that is the ABC of many serious algorithms.

You will use templates, to make your code general enough to sort and search arrays of any type of values for which operator < is defined.

Preliminary facts

1. Let T be a type. The following lines cause the system to allocate an array of n contiguous values of that type. The starting address of this array is stored in ptr,

T * ptr;     // declare a pointer to T
ptr = new T[ n ];

T * ptr = new T[ n ]; 

delete [] ptr; 

2. Class string has all the standard comparison operators such as operator==, operator!=, operator < defined, so you can compare strings as you compare numbers. Strings are ordered, with respect to operator <, in lexicographic order, the one in which words are listed in a dictionary. Due to this, you will be able to sort and search arrays of strings with no extra effort.

A few helper functions

We suggest that you write and test a few helper functions for dealing with arrays before you start programming quicksort and binary search. Here is an example of a template functions:

template< class T >
void print_array( T * a, int len ){
  for( int i=0; i < len; i++ )
    cout << a[i] << " " ;
  cout << endl;
}

print_array( ptr, n );  

We suggest that you write functions for filling your arrays randomly, checking if an array is sorted etc. Your tests should be as few lines of code as possible.

Task I

Write an implementation of Quicksort for an array of integers. If you are not entirely comfortable with templates, we suggest that you don't use them for this task (and add them later when you are sure your program is working. You will need to write the functions

int pivot( int a[], int start, int stop, int pos );  // one turn around the pivot

void quicksort( int a[], int low, int high );        // recursive  

To test these functions, create an array a of integers, fill it with random numbers, apply your quicksort(..) and check if a is indeed sorted now. Repeat the test 100 times :-). Here's what my test code looked like:

  int n;
  cout << "Enter array size: ";
  cin >> n ;

  int* arr = new int[n];

  for( int i=0; i < NUM_TESTS; i++ ){  
      fill_random( arr, n );
      quicksort( arr, 0, n-1 );  // quicksort invoked 
      // print_array( arr, n );  // commented out because it printed too much stuff.
      if( is_sorted( arr, n ) ) cout << "OK ";
      else cout << "ERROR! ";
  }

Task II

Implement the template versions of the functions pivot(..) and quicksort(..) and use them to sort an array of strings. You can enter the strings from the keyboard, or read them from a file. Recall that the following code code will read in a text file, word after word (spaces and newlines are considered word separators and skipped).

  ifstream f( "sometext.txt" );
  string s;
  
  while( f >> s ){  // f >> s fills s with the next word and returns true,
                    //   or fails (when at end of file) and returns false
     do_work_with_word( s );    
  } 

Task III

Implement binary search in the sorted array. Namely, write functions

template< class T > 
bool BinaryFind( T * array , int len, T elt ) 

template< class T > 
bool BinaryFindFirst( T * array , int len, T elt, int & pos ) 

Test your functions interactively a number of times. Reading words from a file, storing them in an array, sorting them and searching for user input words in this array makes a good test. You can use the text fragment from "Alice in Wonderland" for your sample text: alice-proc.txt. See the appendix to the Hash Table extra credit assignment for details about how this text was obtained and prepared.

Task IV (extra credit)

Integrate your code with that for our vector class Table. Add a new method Table< T >::Sort(), which performs Quicksort on the contents of the table. Declare a Table<string>, read in a text file of words, and print the words sorted in alphabetic order.

Change the table by adding an extra array of counters and count how many times each word occurs in the text. Sort the words in the order of their frequency and print the list (now each word is printed once) so oredered.