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