Click here to Skip to main content
15,868,141 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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 />
//Create a class AssortedSorter<br />
class AssortedSorter {<br />
//Attributes of class<br />
private:<br />
		int *intArray;<br />
		int elemCnt;<br />
		<br />
//Member functions<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){
    //initialize reference parameters
    loopCnt=0;
    swapCnt=0;
    
    start=0;
    stop=sz-1;
    //copy array and size
    intArray=arr;
    elemCnt=sz;
    
    int i,s=0, stack[20001];
    stack[s++]=start;
    stack[s++]=stop;
    //sorting the array
    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() {
//Delcare the array and important variables
    int array[MAX_SIZE];
    int userNumOfNumbers;
    //Sequence array will be used for the shell sort algorithm
    int sequence[] = {364, 121, 40, 13, 4, 1, 0};
    int start=0;
    int stop=0;

    srand(time(0));
    //Ask user to enter array size
    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;
    }

    //Generate random numbers to fill the array and seeding the time
    srand(time(0));
    for (int i = 0; i < userNumOfNumbers; i++)
        array[i] = rand() % 1000000 + 1;

    //Create object of the class
    AssortedSorter sorter;
    long int loopCount, swapCount;


    //Display result
    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.
Posted
Updated 7-Oct-22 18:10pm
v2
Comments
jeron1 7-Oct-22 17:28pm    
"does not display every time I run my code" as in the word "Quick" is not displayed? or displaying the wrong values, or something else. Is your quickSort() executing the return statement as it should? Running with a debugger would tell you pretty quickly.

This will probably be a never-ending story.
C++
while (intArray[up] < part)
		loopCnt++;


I would recommend to change or add the following lines. Without limit the user input the static array could be too small.
C++
#define MAX_SIZE  20000
int array[MAX_SIZE];
if (userNumOfNumbers > MAX_SIZE) {
	cout << "Limited number to max " << MAX_SIZE << "\n";
	userNumOfNumbers = MAX_SIZE;
}
srand((unsigned)time(0));

The function srand() should only be called 1x and expects a parameter of type unsigned.
 
Share this answer
 
v5
I have a few observations for your code.

As commented above I don't know what "not always displayed" means. You don't mention the program aborting abnormally which I would think would be quite obvious. Other than that I see no reason the QuickSort results line would not be output. Do you mean the incorrect values are output?

If the results are indeed not output you will need to use your IDE's debugger to find out where things go sideways. If you haven't already, take some time to learn how to compile and run under a debug configuration, how to set/remove a breakpoint, how to step into and step over function calls, and how to inspect the value of a variable or an array. This is time well spent since you're most likely going to spend a lot of time in the debugger - you won't be alone, believe me. It sounds tedious but it beats endlessly adding and removing print statements and recompiling or guessing, praying and hoping.

When stepping thru the code in the debugger you constantly compare what you think should happen with what actually happened at each line. When those results differ, answering "why did that happen?" will tell you a lot.

I would start by placing a breakpoint in main at the line before calling bubbleSort and then stepping over each line after that to ensure each method is being called and each line is being output. If you have a case where program stops or a method doesn't return before or during quickSort it will pinpoint where you need to narrow your search. Then run in debug again but this time step into the offending method.

It appears that once bubbleSort is called there isn't much sorting for Selection, Shell or Quick sorts to do since they are now working with an already sorted array. Does your quickSort method work properly in such a case? Does quickSort go into an infinite loop and just not return until you abort the program yourself?

Look at the comments merano99 made in Solution 1, they may have some bearing on your problem as well.

Other notes (probably not germane to the issue at hand but maybe worth considering at some point):
1) Since the constant sequence array is only used for the shell sort I would consider moving the definition of that array from main to shellSort and no longer pass it as an argument.

2) The same goes for the start and stop integers passed to shellSort and quickSort. In quickSort they are initialized to starting values so any input values are discarded anyway. Just define them inside the method and remove them from main and the argument list. I assume the same holds true for shellSort as well.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900