Quick Sort - stack overflow

This is a discussion on Quick Sort - stack overflow within the C Programming forums, part of the General Programming Boards category; Hello, Can someone let me know why do I get 'stack overflow' error running this code? I suspect that my ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    3

    Quick Sort - stack overflow

    Hello,

    Can someone let me know why do I get 'stack overflow' error running this code? I suspect that my stop condition is wrong, although I cannot see why...since should return when only one element left inthe aray (recursive implementation).

    Thank you all!
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    #define LENGTH 6
    
    //fwd decleration
    void quickSort(int*, int, int);
    int partition(int*, int, int);
    
    int main()
    {
    	int i, a[LENGTH];
    	int left = 0, right = LENGTH-1;
    
    	srand(time(0));
    
    	printf("before:\n");
    	for(i = 0; i < LENGTH; i++)
    	{
    		a[i] = rand()%40+1;
    		printf("%d, ", a[i]);
    	}    
    	printf("\n\n");
    
    	quickSort(a, left, right);
    
    	//print sorted array
    	printf("\nafter:\n");
    	for(i = 0; i < LENGTH; i++)
    		printf("%d, ", a[i]);
    
    	printf("\n\n");
    
    	system("pause");
    	return 0;
    }
    void quickSort(int a[], int left, int right)
    {
    	int mid;
    	//printf("left=%d\t right=%d\n", left, right);
    
    	if(left == right) return;
    	mid = partition(a, left, right);
    	quickSort(a, left, mid-1);
    	quickSort(a, mid+1, right);
    }
    
    int partition(int a[], int left, int right)
    {
    	int p = a[right];
    	int i, j, temp;
    
    	for(i = left, j = i-1; i < right; i++)
    	{
    		if(a[i] <= p)
    		{
    			j++;
    			temp = a[i];
    			a[i] = a[j];
    			a[j] = temp;
    		}
    	}//place pivot
    	temp = a[j+1];
    	a[j+1] = a[right];
    	a[right] = temp;
    	return j+1;
    }

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Probably you have some off by one error and your recursion is infinite. Throw some:
    Code:
    fprintf(stderr, "....
    into the quicksort routines to see how many times they are getting called and with what arguments.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You've got that debug printf statement in there, use it. I got a lot of "left = 2, right = 1" calls when I uncommented that line.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by ButterCup View Post
    ...
    if(left == right) return;
    ...
    Should really be
    Code:
        if (left >= right) return;

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    3
    Quote Originally Posted by itCbitC View Post
    Should really be
    Code:
        if (left >= right) return;
    Thanks...but could you please explain why?
    Can you pls advise how should I print the recursive calls? I'm new to C, and cannot get to the bottom thinking of the recursion idea. Hope it's not too much to ask.
    Thanks again

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I changed that line of code, and it still crashed on me.

    What I don't like, is the partition function.

    Consider this code - no separate partition function, and clear, easy to understand, code imo.

    Code:
    //Quicksort w/o a separate compare function :)
    void quicksort(int A[], int lo, int hi) {
      int i, j, pivot, temp;
    
      if(lo == hi) return; 
      i=lo; 
      j=hi;
      pivot= A[(lo+hi)/2]; 
    
      /* Split the array into two parts */
      do {    
        while (A[i] < pivot) i++; 
        while (A[j] > pivot) j--;
        if (i<=j) {
          //swap(A, i, j);   //this line works fine.
          /* Oddly, on large N, using swap() gives the same time, as
             using the swap code below */
            temp= A[i];
            A[i]= A[j];
            A[j]=temp;
          i++;
          j--;
        }
      } while (i<=j);
        
      if (lo < j) quicksort(A, lo, j);
      if (i < hi) quicksort(A, i, hi);
    }
    The easiest way to think about Quicksort algorithm is the classroom analogy. The teacher wants to line up the 24 pupils, by height.
    so she lines them all up, in the school yard.

    She finds a pupil that's named "pivot", and is about in the middle of the short to tall, heights in the class.

    She has one aide on the right side, and one aide on the left side, and has them walking slowly towards each other, comparing each pupil to the height of "pivot".

    When they find one on the left that is taller, and one on the right side that is shorter, they tell them to swap places in the line, and the aides continue their march toward each other.

    When they meet or cross, perhaps near the middle, (probably not exactly), the two groups (left and right), are compared for size. The smaller group takes two steps forward, and becomes the line that is now treated just like the larger line, before.

    a girl we'll call "pivot" is selected. The left and right side aides, begin walking from their ends of the line, comparing each pupil to "pivot". Like before, when they find someone larger on the left side, and a pupil smaller on the right, they're swapped in the line.
    Like before, when the aides meet near the middle of the line, the left and right side of the line are compared, and the smaller group takes two steps forward, and becomes the new "line".

    This continues until you have the one or two remaining pupils in the "line", in their correct positions, and now the line begins taking two steps backward, rejoining the line directly behind them. This is the if(left==right) return part (or lo == high).

    As every line reforms, the aides remember just where they were, to continue with the older line. (The stack remembers all this bookkeeping stuff in the recursive versions. You have to program your own stack, in iterative versions of Quicksort, and it is a PITA).

    When the lines are all back in the original spot, in one line, the whole class will be sorted.

    Why is Quicksort so quick?

    1) Values can be moved a very long way, in a single swap - compare that to Bubble sort, where the out of order value can only be moved one element over, at a time.

    2) The inner loops for Quicksort are so small and fast:
    Code:
    while(a[i] < pivot) ++i;
    while(a[j] > pivot) --j;
    That's two, one - line loops!

    3) Because it keeps working with data that it just worked with (the older lines become the newer lines). The cache FAST memory is used efficiently. Cache memory is many times faster than regular RAM memory.

    4) Quicksort can be optimized further by using Insertion sort to handle the small "lines" of pupils (small sub arrays).

    One word of caution: Quicksort is *the* most fragile algorithm, I've ever seen. I have some working code for Quicksort that will break if you even look at it funny - and I am NOT kidding -- absolutely BRITTLE, in some implementations.
    Last edited by Adak; 03-20-2010 at 09:18 PM.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by Adak View Post
    One word of caution: Quicksort is *the* most fragile algorithm, I've ever seen. I have some working code for Quicksort that will break if you even look at it funny - and I am NOT kidding -- absolutely BRITTLE, in some implementations.
    That's what unit tests are for!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Mar 2010
    Posts
    3
    Appreciate your help, everyone!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Quick sort in C language (Program required)
    By internet_bug in forum C Programming
    Replies: 4
    Last Post: 09-18-2008, 11:18 PM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 09:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 05:27 PM
  5. stack overflow
    By Unregistered in forum C Programming
    Replies: 29
    Last Post: 08-05-2002, 02:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21