Program to Sort Numbers
Using the QuickSort method

Assignment 9

Modify Assignment 5 to include the timing of the QuickSort.  The quick sort routines should be included in SortRoutines.h and in SortRoutines.cpp.  A timing routine similar to the timing of the Insert sort and the bubble sort should be included in the main program.  The program must be submitted to Dr. Crawford in his office on or before May 2 at 4:30pm.
 

Sample Program Using the Quick Sort

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip.h>

template <class T>
void Partition( T A[], int left, int right, int &mid) {
 int i=left-1, j=right+1;
 T fence = A[(left+right)/2];

 while (i < j) {
  do {
   i++;
  } while (A[i] > fence);

  do {
   j--;
  } while (A[j] < fence);

  T temp = A[i];
  A[i] = A[j];
  A[j] = temp;
 }
 T temp = A[i];
 A[i] = A[j];
 A[j] = temp;

 mid = j;
 

}
 

template <class T>
void QuickSort( T A[], int left, int right) {
 int mid;
 if (left < right) {
  Partition(A, left, right, mid);
  QuickSort(A, left, mid);
  QuickSort(A, mid+1, right);
 }
}

void main() {
 const int Size=100;
 float Array[Size];
 int j;

 srand(time(0));

 for(j=0; j<Size; j++)
  Array[j] = 100*(float)rand()/(float)32767;

 QuickSort(Array, 0, Size-1);

 for(j=0; j<Size; j++) {
  cout << setw(10)<<Array[j]<<"  ";
  if (j % 5 == 4)
   cout << endl;
 }

 cout << endl << endl;

}