Thread: what's wrong with this qsort code?

1. 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;
}```

2. A few remarks:

> quick(array, l, cut);
> quick(array, cut, r);

Should be:

quick(array, l, cut-1);
quick(array, cut+1, r);

In your prof's example code, the recursion will run forever, that is why you get that exception.

And in the swap part of the partition function, I think this:

>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.

3. 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.