Thread: stack overflow

  1. #1
    Registered User
    Join Date
    Dec 2006
    Posts
    14

    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. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Your function is recursive. When you have too much recursion, you break your stack. Pretty simple concept.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    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. #5
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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 ) 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.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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.
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  8. #8
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    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. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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. #10
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    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 .
    Last edited by TechHigh; 01-11-2007 at 05:15 AM.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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
    Last edited by Adak; 01-11-2007 at 05:29 AM.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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
    Last edited by Adak; 01-11-2007 at 02:20 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack overflow errors in 3 areas
    By ulillillia in forum C Programming
    Replies: 13
    Last Post: 04-29-2007, 03:20 PM
  2. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 10:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 06:27 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM