Quick Sort - stack overflow

[ButterCup]

Hello,

Can someone let me know why do I get 'stack overflow' error running this code? I suspect that my stop condition is wrong, although I cannot see why...since should return when only one element left inthe aray (recursive implementation).

Thank you all!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LENGTH 6

//fwd decleration
void quickSort(int*, int, int);
int partition(int*, int, int);

int main()
{
	int i, a[LENGTH];
	int left = 0, right = LENGTH-1;

	srand(time(0));

	printf("before:\n");
	for(i = 0; i < LENGTH; i++)
	{
		a[i] = rand()%40+1;
		printf("%d, ", a[i]);
	}    
	printf("\n\n");

	quickSort(a, left, right);

	//print sorted array
	printf("\nafter:\n");
	for(i = 0; i < LENGTH; i++)
		printf("%d, ", a[i]);

	printf("\n\n");

	system("pause");
	return 0;
}
void quickSort(int a[], int left, int right)
{
	int mid;
	//printf("left=%d\t right=%d\n", left, right);

	if(left == right) return;
	mid = partition(a, left, right);
	quickSort(a, left, mid-1);
	quickSort(a, mid+1, right);
}

int partition(int a[], int left, int right)
{
	int p = a[right];
	int i, j, temp;

	for(i = left, j = i-1; i < right; i++)
	{
		if(a[i] <= p)
		{
			j++;
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}//place pivot
	temp = a[j+1];
	a[j+1] = a[right];
	a[right] = temp;
	return j+1;
}

[MK27]

Probably you have some off by one error and your recursion is infinite. Throw some:

fprintf(stderr, "....

into the quicksort routines to see how many times they are getting called and with what arguments.

[tabstop]

You've got that debug printf statement in there, use it. I got a lot of "left = 2, right = 1" calls when I uncommented that line.

[itCbitC]

...
if(left == right) return;
...

Should really be

    if (left >= right) return;

[ButterCup]

Should really be

    if (left >= right) return;

Thanks...but could you please explain why?
Can you pls advise how should I print the recursive calls? I'm new to C, and cannot get to the bottom thinking of the recursion idea. Hope it's not too much to ask.
Thanks again

[Adak]

I changed that line of code, and it still crashed on me.

What I don't like, is the partition function.

Consider this code - no separate partition function, and clear, easy to understand, code imo.

//Quicksort w/o a separate compare function :)
void quicksort(int A[], int lo, int hi) {
  int i, j, pivot, temp;

  if(lo == hi) return; 
  i=lo; 
  j=hi;
  pivot= A[(lo+hi)/2]; 

  /* Split the array into two parts */
  do {    
    while (A[i] < pivot) i++; 
    while (A[j] > pivot) j--;
    if (i<=j) {
      //swap(A, i, j);   //this line works fine.
      /* Oddly, on large N, using swap() gives the same time, as
         using the swap code below */
        temp= A[i];
        A[i]= A[j];
        A[j]=temp;
      i++;
      j--;
    }
  } while (i<=j);
    
  if (lo < j) quicksort(A, lo, j);
  if (i < hi) quicksort(A, i, hi);
}

The easiest way to think about Quicksort algorithm is the classroom analogy. The teacher wants to line up the 24 pupils, by height.
so she lines them all up, in the school yard.

She finds a pupil that's named "pivot", and is about in the middle of the short to tall, heights in the class.

She has one aide on the right side, and one aide on the left side, and has them walking slowly towards each other, comparing each pupil to the height of "pivot".

When they find one on the left that is taller, and one on the right side that is shorter, they tell them to swap places in the line, and the aides continue their march toward each other.

When they meet or cross, perhaps near the middle, (probably not exactly), the two groups (left and right), are compared for size. The smaller group takes two steps forward, and becomes the line that is now treated just like the larger line, before.

a girl we'll call "pivot" is selected. The left and right side aides, begin walking from their ends of the line, comparing each pupil to "pivot". Like before, when they find someone larger on the left side, and a pupil smaller on the right, they're swapped in the line.
Like before, when the aides meet near the middle of the line, the left and right side of the line are compared, and the smaller group takes two steps forward, and becomes the new "line".

This continues until you have the one or two remaining pupils in the "line", in their correct positions, and now the line begins taking two steps backward, rejoining the line directly behind them. This is the if(left==right) return part (or lo == high).

As every line reforms, the aides remember just where they were, to continue with the older line. (The stack remembers all this bookkeeping stuff in the recursive versions. You have to program your own stack, in iterative versions of Quicksort, and it is a PITA).

When the lines are all back in the original spot, in one line, the whole class will be sorted.

Why is Quicksort so quick?

1) Values can be moved a very long way, in a single swap - compare that to Bubble sort, where the out of order value can only be moved one element over, at a time.

2) The inner loops for Quicksort are so small and fast:

while(a[i] < pivot) ++i;
while(a[j] > pivot) --j;

That's two, one - line loops!

3) Because it keeps working with data that it just worked with (the older lines become the newer lines). The cache FAST memory is used efficiently. Cache memory is many times faster than regular RAM memory.

4) Quicksort can be optimized further by using Insertion sort to handle the small "lines" of pupils (small sub arrays).

One word of caution: Quicksort is *the* most fragile algorithm, I've ever seen. I have some working code for Quicksort that will break if you even look at it funny - and I am NOT kidding -- absolutely BRITTLE, in some implementations.

[iMalc]

One word of caution: Quicksort is *the* most fragile algorithm, I've ever seen. I have some working code for Quicksort that will break if you even look at it funny - and I am NOT kidding -- absolutely BRITTLE, in some implementations.

That's what unit tests are for!

[ButterCup]

Appreciate your help, everyone!