Thread: what's wrong with this qsort code?

Hello everyone,

my Prof. wrote a quicksort source code on the board. We have to implement it in another program. The problem is, the quicksort function raises an exception. I've spent lots of hours to find the error but I still don't know what's wrong.
I am nearly convinced that the Prof. made a mistake ...

Anyway, here is the source code:

Code:

void quick(int array[], int l, int r)
{
	int cut;
	
	if(l < r)
	{
		cut = partition(array, l, r);
		quick(array, l, cut);
		quick(array, cut, r);
	}
}

int partition(int array[], int l, int r)	
{
	int i, j, pivot, tmp;
	
	i = l-1;
	j = r+1;
	pivot = array[l];
	
	while(i < j)
	{
		while(array[++i] < pivot);
		while(array[--j] > pivot);	
											
		if(i < j)							
		{
			tmp = array[i];
	  		array[i] = array[j];
	  		array[j] = tmp;
	  	}
	 }
	 
	 return j;
}

Thank you for your help.

When I use this
> quick(array, l, cut-1);
> quick(array, cut+1, r);

or this
> quick(array, l, cut-1);
> quick(array, cut, r);

the array is sorted incorrectly. But when I use this
> quick(array, l, cut);
> quick(array, cut+1, r);

the quicksort algorithm works.
Thank you very much, Shiro!

>if(i < j)

should be array[i] < array[j], because you want elements with value smaller or equal to pivot left of pivot and elements with value larger or equal to pivot right of pivot.

Hmmm ... I think this is already achieved with the following:
while(array[++i] < pivot);
while(array[--j] > pivot);

array[i] is less than pivot and array[j] is greater than pivot and if ( i < j) the elements can be swapped.