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

---

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.

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


Quzah.

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 :)

Quote:

---

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 :p) 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.

Quote:

---

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.

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.

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 .

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.

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 .

Quote:

---

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.

Adak

Quote:

---

Originally Posted by Adak

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.

Adak

---

He does not need a return statement - Look again!
if (iL<iR) then it does not execute a single other line of code in that fucntion because that is the condition of the if statement. Perhaps he formatted it well enough to see that.
The author obviously chose the single point of function exit sytle of coding.

Looks to me like he breaks out of the for loop, and then the program continues with replacing the pivot, and recursively calling itself, twice more.

I can't wrap my head around the semi-colon after the closing curly brace just after the break statement, though. I freely confess his indentation is a pure curse from hell, for me. It seems like it's sorta normal - and then it's off the road, hurtling over the cliff. I've seen much worse indentation style, that I could follow much easier. :(

Adak