# Quicksort infinite loop

This is a discussion on Quicksort infinite loop within the C++ Programming forums, part of the General Programming Boards category; I am trying to implement quicksort as a sorting algorithm. However, I seem to get an infinite loop. Tried my ...

1. ## Quicksort infinite loop

I am trying to implement quicksort as a sorting algorithm. However, I seem to get an infinite loop. Tried my best to figure it out but couldn't. Any help appreciated. Here is the code.
Code:
```template <typename E>
void TestQucikSort<E>::quickSort(E temparr [], size_t l, size_t r) const {
if(r-l > 1) {
E pivot = temparr[(l+r)/2];
size_t i = l, j = r;
while(i <= j) {
while(pivot > temparr[i]) ++i;
while(temparr[j] > pivot) --j;
if(i <= r) {
std::swap(temparr[i],temparr[j]);
++i;
--j;
}
}
quickSort(temparr,l,j);
quickSort(temparr,i,r);
}
}```

2. Where's the rest of your test program?

Do you have a debugger? Have you tried using it?

3. the rest of the program is pretty long and the problem seems to be with this function. For example if I try to sort an array with values 666, 4711, and 4294967295, I get an infinite loop. Oh and I don't have a debugger, very new to programming, so don't know a lot about that.

4. How hard can it be to just mock up a test program?
Code:
```int main ( ) {
int test[] = { 4711, 4294967295, 666 };
TestQucikSort<int>::quickSort(test, 0, 2);
}```
Create a new project with just a main(), your template and whatever header files needed to make it compile.

> Oh and I don't have a debugger, very new to programming, so don't know a lot about that.
Which compiler/IDE do you have.

If you can't use a debugger, at least put something like
cout << "qsort << l << " " << r << endl;
at the start of the function.

If it's gone into endless recursion, you'll soon see it.

5. Finding out how to use your debugger should be one of the first things to do when learning how to program. Initially you don't have to master every single feature your debugger provides, but at least learn how to single-step through your code, set breakpoints and inspect the values of variables. Trust me, it will save you SOOOO much trouble down the road.

6. I see some problems:
1. If none of the values are less than the pivot and none of them are greater than the pivot, then i and j will not be changed by the inner while loops and the outer while loop will thus loop forever. This would happen when there were say two equal items to sort.

2. Pay attention to your boundary conditions. Is r supposed to be one-past-the-last-item, or the index of the actual last item? If the later, then (r-l > 1) implies that there are two or more items. So exactly two items wont be sorted at all. Note that the "one-past-the-last-item" rule matches what the SC++L does, which turns out to require fewer places where you have to add or subtract 1 here and there.

Those might not be your current problem, but they are certainly something that you need to fix.

Popular pages Recent additions