1. ## stack overflow

I've implemented the quicksort algorithm in Visual Studio 6.0 SP5 in a console project .
It finishes in 0.01 seconds for an array of 1700 elements .For 2000 elements it crashes .
It's probably a stack overflow due to recurrence but I don't know what to do .
Don't tell me to make the variables global .
I give the code below .

Code:
```void quickSort(long *array,long iL,long iR){
long pivot,center,left,right,i,j;
if(iL<iR){
//cautam pivotul si-l punem pe ultima pozitie

center=array[(iL+iR)/2];
left=array[iL];
right=array[iR];
if( (center<left && left<right) || (center>left && left>right) ) //left la mijloc
swap(array,iL,iR);
else
if( (left<center && center<right) || (left>center && center>right) ) //center la mijloc
swap(array,(iL+iR)/2,iR);
pivot=array[iR];
//punem elementele mai mici ca pivotul in stanga si cele mai mari in dreapta
for(;;){
i=iL-1;j=iR;
while(array[++i]<pivot);
while(j>iL && array[--j]>pivot);
if(i<j)
swap(array,i,j);
else
break;
};
swap(array,i,iR);
//apelam recursiv algoritmul asupra celor doua subsiruri
quickSort(array,iL,i-1);
quickSort(array,i+1,iR);
}
}```

2. I don't suppose you could post a minimal complete snippet that demonstrates the problem?

I may have an idea or two, but it's helpful to be able to recreate the bug.

3. Your function is recursive. When you have too much recursion, you break your stack. Pretty simple concept.

Quzah.

4. then quzah , why is this algorithm so higly praised ? The implementation is also copied from a book ...
Dave_Sinkula : it simply acts like going in infinite loop , meaning it enters the algorithm and dies there . I didn't dear to debug on an 2000 numbers input

5. Originally Posted by TechHigh
Dave_Sinkula : it simply acts like going in infinite loop , meaning it enters the algorithm and dies there . I didn't dear to debug on an 2000 numbers input
I have this:
Code:
```long array[1700];

int main(void)
{
size_t i;
srand(time(0));
for ( i = 0; i < sizeof array / sizeof *array; ++i )
{
array[i] = rand();
}
quickSort(array, 0, sizeof array / sizeof *array);
return 0;
}```
Good enough for testing, except I don't have your swap function.

But debugging code generally involves all of the code that demonstrates the issue. Rather than me or others "inventing" code that is sitting right in front of you, it is just easier to strip things down to the bare minimum and find the real reason.

Yes you could be blowing the stack. Or it could be something else. Do you want to fix it, or do you just want to blame this or that?

If you want to fix it and improve your algorithm so that it can handle millions of elements, perhaps post the code?

For example, the following works (for me ) using the standard library's qsort:
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int cmp(const void *a, const void *b)
{
const long *x = a, *y = b;
return (*x > *y) - (*x < *y);
}

void init(long *array, size_t size)
{
size_t i;
for ( i = 0; i < size; ++i )
{
*array++ = rand();
}
}

void print(const long *array, size_t size)
{
size_t i;
for ( i = 0; i < size; ++i )
{
printf("%ld\n", *array++);
}
}

long array[1000000];

int main(void)
{
srand(time(0));
init (array, sizeof array / sizeof *array);
qsort(array, sizeof array / sizeof *array, sizeof *array, cmp);
print(array, sizeof array / sizeof *array);
return 0;
}```
Disclaimer: I never waited for all 1 million values to print.

6. Originally Posted by TechHigh
then quzah , why is this algorithm so higly praised ? The implementation is also copied from a book ...
I didn't praise it. Also, there are loads of crappy books out there. You said you were overflowing your stack. I said if you have too much recursion you tend to overflow your stack. Seems pretty simple to me.

Quzah.

7. it is very hard to read wwith your lack of indentetion. But where is your stop condition?

I don't see a case that you exit your function without entering the recursion.
What will happen when the Ri goes to -1, for example?

PS. Good algorithm and good implementetion is not the same.

8. stop condition is iR==iL and that's all the code I've got .swap is a simple function that swaps the two array elements .

9. Have you verified that it sorts correctly?
It is very simple to write a loop that checks that each item is not greater than its successor.
Then try it on very small lists, say from 2 up to 10.

Make sure that you are passing n-1 for iR, not n, as it looks like your version assumes that iR is one of the elements.
May be good if you can post more code too, like the code that calls this.

10. Yes it works very well for numbers I enter from command line . I've also tried it on about 1800 numers and it worked .When I gave the array the size 2000 the program crashed .
I'll post the code in a few hours , I have to translate the comments in english and I don't have time right now .

11. Originally Posted by TechHigh

Code:
```void quickSort(long *array,long iL,long iR){
long pivot,center,left,right,i,j;
if(iL<iR){
//cautam pivotul si-l punem pe ultima pozitie

center=array[(iL+iR)/2];
left=array[iL];
right=array[iR];

if( (center<left && left<right) || (center>left && left>right) ) //left la mijloc
swap(array,iL,iR);
else
if( (left<center && center<right) || (left>center && center>right) ) //center la mijloc
swap(array,(iL+iR)/2,iR);
pivot=array[iR];

//punem elementele mai mici ca pivotul in stanga si cele mai mari in dreapta
for(;;){
i=iL-1;j=iR;
while(array[++i]<pivot);
while(j>iL && array[--j]>pivot);
if(i<j)
swap(array,i,j);
else
break;
};
swap(array,i,iR);
//apelam recursiv algoritmul asupra celor doua subsiruri
quickSort(array,iL,i-1);
quickSort(array,i+1,iR);
}
}```

I don't see a return statement, at all. If the sub array being sorted has less than two elements, it needs to return:

Code:
```
if (left >= right)
return;```
Recursive Quicksort will easily handle your array's numbers. You just need to get it set up right. Your basic Quicksort is similar to K&R's second edition, on page 87. If you can't get yours figured out, you might want to look at or use K&R's version.

I don't see a return statement, at all. If the sub array being sorted has less than two elements, it needs to return:

Code:
```
if (left >= right)
return;```
Recursive Quicksort will easily handle your array's numbers. You just need to get it set up right. Your basic Quicksort is similar to K&R's second edition, on page 87. If you can't get yours figured out, you might want to look at or use K&R's version.