// // demonstrates a QuickSort sorting algorithm // // Algorithm taken from the pseudo code presented in p.154: // Cormen, Thomas H., et al. Introduction to Algorithms. // The MIT Press, 1990. // // // Written by Maxwell Sayles, 2001, for CPSC331, University of Calgary. // #include #include #include using namespace std; const int numElements = 128; // number of elements to sort int Partition (int* A, int p, int r) { int x = A[p]; // this is the pivot value ... any value between the highest and lowest would work as well (e.g. A[(p+r)/2]) int i = p-1; // we start i one index below, because when we scan right we increment first, then test int j = r+1; // same reason we start j one index above while (true) { do { j--; } // start right, scan left until a value less than x is found while (A[j] > x); do { i++; } // start left, scan right until a value greater than x is found while (A[i] < x); if (i < j) { // exchange A[i] with A[j] int temp = A[i]; A[i] = A[j]; A[j] = temp; } else return j; } } void QuickSort (int* A, int p, int r) { if (p < r) { int q = Partition (A, p, r); QuickSort (A, p, q); QuickSort (A, q+1, r); } } // // program entry // int main() { int i = 0; // seed the random number generator srand((unsigned int)time(0)); // create an array of random integers int array[numElements]; for (i = 0; i < numElements; i ++) { array[i] = rand() % numElements; // keep numbers in the range of 0-numElements } // sort the array QuickSort (array, 0, numElements-1); // print the array for (i = 0; i < numElements; i ++) { cout << array[i] << ' '; } cout << endl; return 0; }