I have programmed the first 2 algorithms (qsf, qsl) which have

**run quite well for ALL input sizes when provided with a random input sequence**. However, when they are fed all equivalent keys (all elements in array are 32.25), decreasing, and even increasing input sequences, the program seems to stall for a bit and then windows gives an error. I raw code in Notepad++, but use Visual Studio's debugger which is telling me I am getting a stack overflow in these cases.

**Note:**These 3 input types DO work up to an input size of about 43400 (I tested a bunch of times and they don't seem to work past 43400) and, strangely enough, the longest runner is the "all equivalent" input sequence.

Here's most of the code (I left out the utility functions to save space). My professor asked that we use simple command line arguments for the inputs (using 1-4 as options for each of the specifiable command line arguments. This is why I have all the code for converting argv to integers etc.) He also wants us to use the array range 1 to n instead of 0 to n-1.

int main(int argc, char** argv){ //make sure all arguments are present if(argc != 4){ errorMessage(argv[0]); return 0; } //cast the arguments to integers int algorithmPointer = *argv[1] - '0'; int problemPointer = *argv[2] - '0'; int sequencePointer = *argv[3] - '0'; //make sure all arguments are within the acceptable range if(algorithmPointer < 1 || algorithmPointer > 4 || problemPointer < 1 || problemPointer > 4 || sequencePointer < 1 || sequencePointer > 4){ errorMessage(argv[0]); return 0; } char algorithmChooser[][5] = {"null", "qsf", "qsl", "qsm", "qsr"}; char* algorithmTitle = algorithmChooser[algorithmPointer]; int nChooser[5] = {0, 64000, 256000, 1024000, 8192000}; int n = nChooser[problemPointer]; char sequenceChooser[][20] = {"null", "random", "all keys equivalent", "decreasing sequence", "increasing sequence"}; char* sequenceTitle = sequenceChooser[sequencePointer]; cout << "\nChosen algorithm is: " << algorithmTitle << endl; cout << "Chosen problem size (n) is: " << n << endl; cout << "Chosen sequence is: " << sequenceTitle << endl; //setup the key list array double *A = new double[n+1]; setupKeys(A, sequencePointer, n); //declare variables to hold timer values double timeIn, timeOut; //call the algorithm according to the command line argument switch(algorithmPointer){ case 1: timeIn = getTime(); qsf(A, 1, n); timeOut = getTime(); break; case 2: timeIn = getTime(); qsl(A, 1, n); timeOut = getTime(); break; /*case 3: timeIn = getTime(); qsm(A, 1, n); timeOut = getTime(); break; case 4: timeIn = getTime(); qsr(A, 1, n); timeOut = getTime(); break;*/ } cout << endl << "Total time: " << (timeOut - timeIn)/CLOCKS_PER_SEC << " seconds\n"; delete[] A; return 0; } /************************************************************ ***************************QSF******************************* ************************************************************/ void qsf(double *A, int left, int right){ if (left < right){ int pivotPoint = partitionQSF(A, left, right); //get pivotPoint from the partition function & partition qsf(A, left, pivotPoint - 1); //recursive call for values <= pivot qsf(A, pivotPoint + 1, right); //recursive call for values > pivot } } int partitionQSF(double *A, const int &p, const int &r){ //store the pivot value (in this case it is the first key) double pivot = A[p]; swap(A[p], A[r]); //swap the pivot value with the last term for safe keeping int i = p - 1; //initialize the counter which counts the # of terms <= pivot //scan left -> right and partition based on comparing to pivot for (int currentIndex = p; currentIndex <= r - 1; currentIndex++){ if(A[currentIndex] <= pivot){ //increment the counter & perform swap i++; swap(A[i], A[currentIndex]); } } swap(A[i + 1], A[r]); //place the pivot where it belongs in the array return (i + 1); //return the position of the pivot } /************************************************************ ***************************QSL******************************* ************************************************************/ void qsl(double *A, int p, int r){ if (p < r){ int q = partitionQSL(A, p, r); qsl(A, p, q - 1); qsl(A, q + 1, r); } } int partitionQSL(double *A, const int &p, const int &r){ double pivot = A[r]; int i = p - 1; for (int j = p; j <= r - 1; j++){ if(A[j] <= pivot){ i++; swap(A[i], A[j]); } } swap(A[i + 1], A[r]); return (i + 1); }

And here's the code I used to populate the array:

void setupKeys(double *keys, const int &choice, const int &range){ switch(choice){ case 1: srand(time(NULL)); for(int i = 1; i <= range; i++){ double randomNum = (double)(rand() % range) + getRand(); keys[i] = randomNum; } break; case 2: for(int i = 1; i <= range; i++){ keys[i] = 32.25; } break; case 3: for(int i = 1; i <= range; i++){ keys[i] = (double)(range - i); } break; case 4: for(int i = 1; i <= range; i++){ keys[i] = (double)(i + 1); } break; } }

Thanks ahead for any help solving this!

This post has been edited by **axnjxn**: 05 February 2013 - 07:42 PM