- #1
KLoux
- 176
- 1
Hello. I've been reading up on sorting algorithms, and decided to try writing a quicksort algorithm. After a bit of debugging, I got it working, but when I increase the size of my data set, I get a stack overflow. To sort an array with 100 elements, I sometimes get a stack overflow, but with 1000 elements, I consistently get an overflow.
I know that pivot choice can have an effect on how many recursive calls to my sort I need to make, but I am choosing a random pivot, which many sources say is a good way to reduce the chance of hitting the worst case performance. Is this something anyone else has run into with quicksort? I quick google search suggests I am not the only one to have this problem, but beyond "there is probably something wrong with your algorithm" it hasn't helped much.
Is there something wrong here? What is the size of the stack? Can I change it? Should I change it? I understand if you don't want to debug my code, but I would be very appreciative if you can offer some general suggestions.
Here is my code:
Thanks in advance!
-Kerry
I know that pivot choice can have an effect on how many recursive calls to my sort I need to make, but I am choosing a random pivot, which many sources say is a good way to reduce the chance of hitting the worst case performance. Is this something anyone else has run into with quicksort? I quick google search suggests I am not the only one to have this problem, but beyond "there is probably something wrong with your algorithm" it hasn't helped much.
Is there something wrong here? What is the size of the stack? Can I change it? Should I change it? I understand if you don't want to debug my code, but I would be very appreciative if you can offer some general suggestions.
Here is my code:
Code:
void DoQuickSort(int *Array, const int ArraySize, bool HighToLow)
{
// If there is nothing to sort, don't do anything
if (ArraySize <= 1)
return;
// Pick a random pivot
int PivotLocation = rand() % ArraySize;
int Pivot = Array[PivotLocation];
// Swap the pivot with the number at the beginning of the array
int SwapValue = Array[ArraySize - 1];
Array[ArraySize - 1] = Pivot;
Array[PivotLocation] = SwapValue;
// Split the array into two groups: Higher than pivot and lower than pivot
int SortedElements = 0;
int NumberOfTopElements = 0;
while (SortedElements < ArraySize)
{
// Check to see if the element is larger or smaller than the pivot
// and if we are sorting in ascending or descending order
if ((Array[SortedElements] > Pivot && HighToLow) ||
(Array[SortedElements] < Pivot && !HighToLow))
{
// Swap this element with the next element toward the top of the list
SwapValue = Array[NumberOfTopElements];
Array[NumberOfTopElements] = Array[SortedElements];
Array[SortedElements] = SwapValue;
NumberOfTopElements++;
}
// Increment the number of elements we've sorted
SortedElements++;
}
// Place our pivot in the right location (this is the last time the pivot will be moved)
SwapValue = Array[NumberOfTopElements];
Array[NumberOfTopElements] = Array[ArraySize - 1];
Array[ArraySize - 1] = SwapValue;
// Call this recursively on the two new lists
DoQuickSort(Array, NumberOfTopElements, HighToLow);
DoQuickSort(Array + NumberOfTopElements, ArraySize - NumberOfTopElements, HighToLow);
return;
}
Thanks in advance!
-Kerry