Thread: 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!

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

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