recursive quick sort - stack overflow

This is a discussion on recursive quick sort - stack overflow within the C Programming forums, part of the General Programming Boards category; Hello, I compared time of execution of different sort algorithm. I cam accross on interesting thing about quick sort algorithm. ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

    recursive quick sort - stack overflow

    Hello, I compared time of execution of different sort algorithm.
    I cam accross on interesting thing about quick sort algorithm.
    Consider this code pay attention on function partition:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    #define N 10000
    
    void quick_sort(int*, int, int);
    int partition(int*, int, int);
    int median(int*,int,int);
    
    int main(void)
    {
    	int array[N];
    	int i;
    	clock_t start, end;
    	double duration;
    	
    	for(i=0;i<N;i++)
    		array[i]=rand();
    	quick_sort(array,0,N-1);
    	
    	start=clock();
    	quick_sort(array,0,N-1);
    	end=clock();
    	
    	duration=1000*(double)(end-start)/CLOCKS_PER_SEC;
    	printf("\n%.3lf",duration);
    }
    
     void quick_sort(int* array,int l,int r)
     {
    	 int j;
    	 if(r<=l) return;
    	 j=partition(array,l,r);
    	 quick_sort(array,l,j-1);
    	 quick_sort(array,j+1,r);
     }
    
     int partition(int* array, int l, int r)
     {
    	 int pivot,i,j,tmp;
    	/*here is important point*/
    	 tmp=median(array,l,r);
                     pivot=array[tmp];
    	 
    	 /*pivot=array[l];*/
    	 i=l+1;
    	 j=r;
    	
    	
    	 for(;;)
    	 {
    		 while((array[i] <= pivot) && (i <= r))
    			 i++;
    		 while((array[j] > pivot) && (j > l))
    			 j--;
    		 if(i < j)
    		 {
    			 
    			 tmp=array[i];
    			 array[i]=array[j];
    			 array[j]=tmp;
    		 }
    		 else 
    			 break;
    	 }
    	 
    	 tmp=array[l];
    	 array[l]=array[j];
    	 array[j]=tmp;
    	
    	 return j;
     }
    
    int median (int* arr, int l, int r)
           {
              int c=(l+r)/2;
               if ((arr[l] > arr[c] && arr[c] > arr[r]) || (arr[r] > arr[c] && arr[c] > arr[l]))
                   return c;          
               if ((arr[c] > arr[r] && arr[r] > arr[l]) || (arr[l] > arr[r] && arr[r] > arr[c]))
                   return r;           
               return l;
           }
    If I execute code that use function median I get average time of execution (when array is already sorted - worst case)this algorithm 100 ms.
    But if I choose not to use median of three function and choose pivot as simply first array element I get exception stack overflow. I'm using Visual Studio .Net. I conclude this is because of recursion in quick_sort. Because choosing first element I'm basically dividing array in two nonequal size arrays, bigger array will have 9999 elements to be sorted using recursion.

    I know I might overcome this problem using median function and/or explicit stack with nonrecursive implementation of quick sort.

    Is there any possibility that stack size is limited in visual studio to some fixed value and will this code have the same problem on using some other compiler. Can you execute it so we can compare results.
    I wonder if this way of measuring time of execution correct. For example if I get result 150 milliseconds what is fault tolerance when using clock() function?
    I was learning a lot about different type of sorting algorithms and found good infos in Prelude's corner but I think job isn't finished. I'm willing to write a small tutorial about bubble, selection, insertion and quick sort with algorithm analysis and measuring time of execution, but not sure if there are people interested to read that. And secondly, if there is need for that I'll need someone to examine and correct tutorial because English is not my native language.
    Please tell me your opinion about this idea.
    Cheers!
    Last edited by Micko; 01-02-2005 at 02:27 AM. Reason: there was a bug in function median()

  2. #2
    RoD
    RoD is offline
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331
    >Is there any possibility that stack size is limited
    If your algorithm is using up the stack then that means there's something wrong with the algorithm, not the environment. Of course, you could be hitting a pathological worst case out of sheer dumb luck. Try seeding the random number generator with something different than the default.

  3. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Quote Originally Posted by RoD
    >Is there any possibility that stack size is limited
    If your algorithm is using up the stack then that means there's something wrong with the algorithm, not the environment. Of course, you could be hitting a pathological worst case out of sheer dumb luck. Try seeding the random number generator with something different than the default.
    Pay attention that I measure execution time of worst case. My intention was to analyze worst case, that's why I sorted array before starting time measurement. I know why stack overflow occurs but I'm interested to see how much stack space is reserved for my program and is it compiler specific or something else?

  4. #4
    RoD
    RoD is offline
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331
    >but I'm interested to see how much stack space is reserved for my program
    Read your compiler's documentation.

  5. #5
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,659
    > but I'm interested to see how much stack space is reserved for my program

    well, if it's a Windows program:

    Code:
    unsigned seekToStackReserve(FILE * file) {
     unsigned offset; 
     fseek(file, 0x3c, SEEK_SET);
     if(ftell(file) == 0x3c) { 
      if(fread(&offset, sizeof(offset), 1, file)) {
       offset += 0x60;
       fseek(file, offset, SEEK_SET);
       if(ftell(file) == offset) {
        return offset;
        }
       }  
      }
     return 0; 
     }
    
    unsigned getStackReserve(FILE * in) {
     unsigned size = 0;
     if(seekToStackReserve(in)) {
      if(fread(&size, sizeof(size), 1, in)) {
       return size;
       }
      }
     return 0; 
     } 
    
    int setStackReserve(FILE * out, unsigned size) {
     if(seekToStackReserve(out)) {
      if(fwrite(&size, sizeof(size), 1, out)) {
       return 1;
       }
      }
     return 0; 
     } 
     
    int main(int, char ** argv) {
     FILE * fp;
     unsigned size;
     while(*(++argv)) {
      fp = fopen(*argv, "rb");
      if(fp) {
       size = getStackReserve(fp);
       if(size) {
        printf("Stack reserve for file '%s' is: %u.\n", *argv, size); 
        } else {
        printf("File '%s' is not a valid executable.\n", *argv); 
        }    
       fclose(fp); 
       } else {
       printf("Could not open file '%s'.\n", *argv); 
       } 
      }
     }



    ITSA
    Socket Library!

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,659
    this version does a better job of validation:

    Code:
    unsigned seekToStackReserve(FILE * file) {
     unsigned offset; 
     char sig[2];
     fseek(file, 0x0, SEEK_SET);
     if(ftell(file) == 0x0 && fread(sig, 2, 1, file) 
     && sig[0] == 'M' && sig[1] == 'Z') {
      fseek(file, 0x3c, SEEK_SET);
      if(ftell(file) == 0x3c && fread(&offset, sizeof(offset), 1, file)) {
       fseek(file, offset, SEEK_SET);
       if(ftell(file) == offset && fread(sig, 2, 1, file) 
       && sig[0] == 'P' && sig[1] == 'E') {
        offset += 0x60;
        fseek(file, offset, SEEK_SET);
        if(ftell(file) == offset) {
         return offset;
         }
        } 
       }  
      }
     return 0; 
     }



    ITSA
    Socket Library!

  8. #8
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Thank you all for replies. You helped me a lot.
    What about second question?

  9. #9
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    The idea of reporting the state of the stack at run-time interested me. N.B: This is not production code, it makes several dangerous assumptions. It could be of use in debugging.
    Code:
    #include <windows.h>
    #include <stdio.h>
    
    void StackReport(void)
    {
    	BYTE stackVariable;
    	MEMORY_BASIC_INFORMATION mbi;
    	LPBYTE queryAddress;
    
    	/* First get the base address of the memory reserved for the stack. */
    
    	queryAddress = &stackVariable;
    	VirtualQuery(queryAddress, &mbi, sizeof(mbi));
    
    	/* Stack grows upwards. So going from top to bottom we have reserved space,
    	 * a guard page and finally committed memory. */
    
    	queryAddress = mbi.AllocationBase;
    	VirtualQuery(queryAddress, &mbi, sizeof(mbi));
    	printf("%u bytes of reserved stack space remains.\n", mbi.RegionSize);
    
    	queryAddress += mbi.RegionSize;
    	VirtualQuery(queryAddress, &mbi, sizeof(mbi));
    	printf("%u bytes of guard pages.\n", mbi.RegionSize);
    	
    	queryAddress += mbi.RegionSize;
    	VirtualQuery(queryAddress, &mbi, sizeof(mbi));
    	printf("%u bytes of committed stack.\n\n", mbi.RegionSize);
    }
    
    void func2(void)
    {
    	BYTE stackWaste[128 * 1024] = { 0 }; /* Use up 128KB of stack space. */
    	lstrlen(stackWaste);  /* Touch stackWaste so it is not optimised out. */
    
    	printf("In func2...\n");
    	StackReport();        /* Report the current state of the stack. */
    }
    
    void func1(void)
    {
    	BYTE stackWaste[70 * 1024] = { 0 };
    	lstrlen(stackWaste);
    
    	printf("In func1...\n");
    	StackReport();
    	func2();
    }
    
    int main(void)
    {
    	printf("In main...\n");
    	StackReport();
    
    	func1();
    
    	printf("Back in main...\n");
    	StackReport();
    
    	getchar();
    	return 0;
    }
    Result:
    Code:
    In main...
    1015808 bytes of reserved stack space remains.
    4096 bytes of guard pages.
    28672 bytes of committed stack.
    
    In func1...
    970752 bytes of reserved stack space remains.
    4096 bytes of guard pages.
    73728 bytes of committed stack.
    
    In func2...
    839680 bytes of reserved stack space remains.
    4096 bytes of guard pages.
    204800 bytes of committed stack.
    
    Back in main...
    839680 bytes of reserved stack space remains.
    4096 bytes of guard pages.
    204800 bytes of committed stack.
    P.S. No, this post doesn't answer any of your questions.

  10. #10
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Interesting, but I'm pretty much satisfied with that msdn article.
    Your last post I can't follow, but I'm sure there are a lot of guys here who will know to appreciate it!
    Thanks anyway

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack overflow with sqrtf
    By Skusey in forum C++ Programming
    Replies: 8
    Last Post: 10-05-2006, 03:39 AM
  2. Quick Sort Help
    By NavyBlue in forum C Programming
    Replies: 1
    Last Post: 03-02-2003, 09:34 PM
  3. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM
  4. What am I doing wrong, stack?
    By TeenyTig in forum C Programming
    Replies: 2
    Last Post: 05-27-2002, 02:12 PM
  5. stack make file problem
    By puckett_m in forum C Programming
    Replies: 2
    Last Post: 11-22-2001, 10:51 AM

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