Quicksort crashes on large increasing arrays
I'm doing an analysis on different sorting algorithms with different types of integer arrays (random, increasing, decreasing, nondecreasing, nonincreasing). Below I've pulled my quicksort and a test case out.
When my array goes over ~4500 elements on a increasing array the program crashes, works fine on large random arrays. I'm assuming I'm reaching some limit do to my recursion going so deep.The code works as is on my compiler(visual studio 2005), but if I increase my array by one more element the program crashes.The quicksort is created from pseudocode found in my algorithms book, which uses the first element as the split, making my increasing array lopsided, if I change the split to (l+r)/2 all is fine. I would like to maintain the split using the first element. Any help is much appreciated. I'm open to other quicksort algorithms, but I've tried several others and the same thing eventually happens. My largest test case goes up to 10^5 so I have a ways to go. Any one have any ideas as how to correct, or what may be going wrong?
#include <iostream>
using namespace std;
void quickSort(int array[], int l, int r, int &basic);
int partition(int array[],int l, int r, int &basic);
int main()
{
int basic=0;
int test[4245];
for (int i=0;i<4245;i++)
test[i]=i;
quickSort(test,0,4244,basic);
cout<<basic<<endl;
return 0;
}
void quickSort(int array[],int l, int r, int &basic)
{
int split;
if(l<r)
{
split=partition(array,l,r,basic);
quickSort(array,l,split-1,basic);
quickSort(array,split+1,r,basic);
}
}
int partition(int array[],int l, int r, int &basic)
{
int p,i,j,tmp;
p=array[l];
i=l;
j=r+1;
do
{
do
{
basic++;
i++;
}
while(array[i]<p);
do
{
basic++;
j--;
}
while(array[j]>p);
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
while(i<j);
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
tmp=array[l];
array[l]=array[j];
array[j]=tmp;
return j;
}
When my array goes over ~4500 elements on a increasing array the program crashes, works fine on large random arrays. I'm assuming I'm reaching some limit do to my recursion going so deep.The code works as is on my compiler(visual studio 2005), but if I increase my array by one more element the program crashes.The quicksort is created from pseudocode found in my algorithms book, which uses the first element as the split, making my increasing array lopsided, if I change the split to (l+r)/2 all is fine. I would like to maintain the split using the first element. Any help is much appreciated. I'm open to other quicksort algorithms, but I've tried several others and the same thing eventually happens. My largest test case goes up to 10^5 so I have a ways to go. Any one have any ideas as how to correct, or what may be going wrong?
#include <iostream>
using namespace std;
void quickSort(int array[], int l, int r, int &basic);
int partition(int array[],int l, int r, int &basic);
int main()
{
int basic=0;
int test[4245];
for (int i=0;i<4245;i++)
test[i]=i;
quickSort(test,0,4244,basic);
cout<<basic<<endl;
return 0;
}
void quickSort(int array[],int l, int r, int &basic)
{
int split;
if(l<r)
{
split=partition(array,l,r,basic);
quickSort(array,l,split-1,basic);
quickSort(array,split+1,r,basic);
}
}
int partition(int array[],int l, int r, int &basic)
{
int p,i,j,tmp;
p=array[l];
i=l;
j=r+1;
do
{
do
{
basic++;
i++;
}
while(array[i]<p);
do
{
basic++;
j--;
}
while(array[j]>p);
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
while(i<j);
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
tmp=array[l];
array[l]=array[j];
array[j]=tmp;
return j;
}
Last edited on
Your array is almost filling the stack, and quicksort is finishing the job. Try allocating the array on the heap.
helios,
Thanks for the quick response. Still not getting much farther than before. I may have to just switch the pivot, or find an iterative quick sort.
Thanks for the quick response. Still not getting much farther than before. I may have to just switch the pivot, or find an iterative quick sort.
Topic archived. No new replies allowed.