Quick Sort Results in Infinite Loop

Question

I have tried everything. Even have found an online example that is exactly like mine. Every time I run this quick sort it results in an infinite loop, and I am so stuck. Can someone please help? I'm simply passing an array through like normal, and cant get this think to work. Also ignore the timing aspect, thats for the project, timing the sort.

template<typename T>
void quickSort(T list[], int lowerBound, int upperBound)
{
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(16);

    TimerSystem timer;
    timer.startClock();

    upperBound = upperBound - 1;

    long int i = lowerBound;
    long int j = upperBound;
    long int pivot = list[(lowerBound + upperBound) / 2];
    T temp;

    while (i <= j)
    {
        while (list[i] < pivot)
        {
            i += 1;
        }

        while (list[j] > pivot)
        {
            j -= 1;
        }

        if (i <= j)
        {
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            i += 1;
            j -= 1;
        }
    }

    if (lowerBound < j)
    {
        quickSort(list, lowerBound, j);
    }

    if (i < upperBound)
    {
        quickSort(list, i, upperBound);
    }


    cout << "USE FINAL TIME RECORDING!! QuickSort took " << timer.getTime() << "seconds to sort" << endl;
    cout << endl;
}

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) — Max Vollmer, Sep 30 '19 at 01:40
*I have tried everything.* -- [Did you really try *everything*?](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). You also need to post a `main` program calling your function with actual test data. It is not clear what `lowerBound` and `upperBound` are supposed to be. — PaulMcKenzie, Sep 30 '19 at 02:46
I have a main driver program. I did five other sorting algorithms, but this one will not work. I have no idea why. I think it might be a recursion problem? But I cant find where the issue lies — ColtTheNark, Sep 30 '19 at 02:50
So why are you not posting a simple call to your quicksort function with sample data, following the guidelines here on posting a [mcve]? We have no idea what those values you're passing are or what they're supposed to denote. You've rejected one answer already, and to not waste more time, it is more helpful if we see an entire sample call to your function. — PaulMcKenzie, Sep 30 '19 at 03:05
First, I apologize, seriously, I am a new programming student and new to stack overflow. I didn't know there were guidelines. I just wanted some simple help. I apologize, again. The data is simple integers passed through an array. That's all, which is why i am so confused — ColtTheNark, Sep 30 '19 at 03:06
@ColtTheNark No, it isn't just "simple integers". You have two other parameters, `lowerBound` and `upperBound`. We do not know what these values are supposed to mean. What if the issue are those two (so far to us) unknown values? — PaulMcKenzie, Sep 30 '19 at 03:07
Lowerbound and upperbound are the first and last items (or sections really) of the array. If the size of the array is 100, then lowerbound is 0 and upperbound is 100 — ColtTheNark, Sep 30 '19 at 03:17
Also, again, I'm sorry, I did not mean to 'reject' any answers, I have been reading the link that was sent in the comment. I feel like I have upset you and for that I really am sorry, I'm a stressed student new to all of this — ColtTheNark, Sep 30 '19 at 03:19
[This is an example of what is expected](http://coliru.stacked-crooked.com/a/54d4fad520964930). It is minimal, it is complete, and it shows the error. The first comment about using the debugger should now come into play, given that a simple sort of 4 numbers is failing. — PaulMcKenzie, Sep 30 '19 at 03:27
@PaulMcKenzie - your example won't catch one of the mistakes in the code. — rcgldr, Sep 30 '19 at 12:42
My example was not meant to be an answer. It was meant to show the OP how to post a [mcve]. The OP can add or remove lines of code, change data, etc. and repost it here if need be. — PaulMcKenzie, Sep 30 '19 at 12:43
There is always risk of infinite recursion in Quicksort depending on the partition scheme used, See Partition Schemes in [Quicksort-wikipedia](https://en.wikipedia.org/wiki/Quicksort) — David C. Rankin, Sep 30 '19 at 18:42

score 0 · Answer 1 · answered Sep 30 '19 at 01:47

0

From the first sight,

while (i <= j)

looks suspicious, please replace it with

while (i < j)

and try again.

answered Sep 30 '19 at 01:47

lenik

23,228
4
34
43

yes I fixed this, no solution though :/ thank you though! – ColtTheNark Sep 30 '19 at 02:05
I think the problem is elsewhere. – rcgldr Sep 30 '19 at 10:36

rcgldr · Answer 2 · 2019-10-01T13:00:20.687

Since the code is using cout.precision(16), I'm assuming that list[] is an array of floats or doubles. However, pivot is defined to be type long int when it should be type T:

    T pivot = list[(lowerBound + upperBound) / 2];

Having pivot typed as long int would explain the infinite loop, since the inner while loops rely on stopping if either list[i] == pivot and/or list[j] == pivot, which won't happen if the actual pivot: list[(lowerBound + upperBound) / 2] is not exactly equal to an integer.

Another problem is upperbound = upperbound - 1; This will occur on the initial and every recursive instance of quickSort. Instead, that statement should be deleted, and the initial call for a list of size N should be

    quickSort(list, 0, N-1);

There is no need for i and j to be typed as long int, just typed as int is good enough, but this isn't causing any problems.

Quick Sort Results in Infinite Loop

2 Answers2