# Thread: recursive quick sort - stack overflow

1. ## 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.
Cheers!

2. >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. 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. >but I'm interested to see how much stack space is reserved for my program

5. > 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) {
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)) {
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);
}
}
}```

6. 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;
}```

7. Thank you all for replies. You helped me a lot.

8. 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;

/* First get the base address of the memory reserved for the stack. */

/* Stack grows upwards. So going from top to bottom we have reserved space,
* a guard page and finally committed memory. */

printf("%u bytes of reserved stack space remains.\n", mbi.RegionSize);

printf("%u bytes of guard pages.\n", mbi.RegionSize);

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.```