I am currently working on a program that tests the speed and efficiency of four different sorting methods. Every sorting function will have a loop count and a swap count. I created a class in one file and implemented the member function in another. In the main file, I ask the user to input the size for an array for all the functions to sort. However, the last sorting method (quick sort) does not display every time I run my code. Here is my program
<br />
class AssortedSorter {<br />
private:<br />
int *intArray;<br />
int elemCnt;<br />
<br />
public:<br />
void bubbleSort(int[], int, long int&, long int&);<br />
void selectionSort(int[], int, long int&, long int&);<br />
void shellSort(int[], int[], int, int, int, long int&, long int&);<br />
void quickSort(int[], int, int, int, long int&, long int&);<br />
int partition(int[], int, int, int, long int&, long int&);<br />
};
The following is a quick sort function that implements the partition function with in it.
void AssortedSorter::quickSort(int arr[], int sz, int start, int stop, long int& loopCnt, long int& swapCnt){
loopCnt=0;
swapCnt=0;
start=0;
stop=sz-1;
intArray=arr;
elemCnt=sz;
int i,s=0, stack[20001];
stack[s++]=start;
stack[s++]=stop;
while(s>0) {
stop = stack[--s];
start = stack[--s];
if (start >= stop)continue;
i = partition(intArray, elemCnt, start, stop, loopCnt, swapCnt);
if (i - start > stop - 1) {
stack[s++] = start;
stack[s++] = i - 1;
stack[s++] = i + 1;
stack[s++] = stop;
} else {
stack[s++] = i + 1;
stack[s++] = stop;
stack[s++] = start;
stack[s++] = i - 1;
}
}
}
The following is the partition function that performs the swapping of the array
int AssortedSorter::partition(int arr[], int sz, int start, int stop, long int& loopCnt, long int& swapCnt) {
intArray = arr;
elemCnt = sz;
int up = start, down = stop - 1, part = intArray[stop];
if (stop <= start)
return start;
while (true) {
while (intArray[up] < part)
loopCnt++;
up++;
while ((part < intArray[down]) & (up < down))
loopCnt++;
down--;
if (up >= down)
break;
swapCnt++;
swap(intArray[up], intArray[down]);
up++;
down--;
}
swapCnt++;
swap(intArray[up], intArray[down]);
return up;
}
The following is the main function
int main() {
int array[MAX_SIZE];
int userNumOfNumbers;
int sequence[] = {364, 121, 40, 13, 4, 1, 0};
int start=0;
int stop=0;
srand(time(0));
cout << "Enter number between 10 to 20000 for the number of elements in the array"<<endl;
cout << "Or press 0 and we choose for you: ";
cin >> userNumOfNumbers;
if(userNumOfNumbers == 0) {
cout << "The number I have chosen is 10000";
userNumOfNumbers = 10000;
}
srand(time(0));
for (int i = 0; i < userNumOfNumbers; i++)
array[i] = rand() % 1000000 + 1;
AssortedSorter sorter;
long int loopCount, swapCount;
cout << "\nSORT ALGORITHM RUN EFFICIENCY" << endl;
cout << "ALGORITHM\tLOOP COUNT\tDATA MOVEMENT" << endl;
sorter.bubbleSort(array, userNumOfNumbers, loopCount, swapCount);
cout << "Bubble\t\t" << loopCount << "\t\t" << swapCount << endl;
sorter.selectionSort(array, userNumOfNumbers, loopCount, swapCount);
cout << "Selection \t" << loopCount << "\t\t" << swapCount << endl;
sorter.shellSort(array, sequence, userNumOfNumbers, start, stop, loopCount, swapCount);
cout << "Shell \t\t" << loopCount << "\t\t" << swapCount<<endl;
sorter.quickSort(array, userNumOfNumbers, start, stop, loopCount, swapCount);
cout << "Quick \t\t" << loopCount << "\t\t" << swapCount << endl;
return 0;
}
What I have tried:
One thing I thought that could have been the problem is that my loopCnt and swapCnt are not returning their values back to the quicksort function. I tried to use pointers to alter with the value, but that didn't work.