Thread: 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);
		}
}

Where's the rest of your test program?

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

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.

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.