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.(adsbygoogle = window.adsbygoogle || []).push({});

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!Code (Text):

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;

}

-Kerry

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Stack Overflow with Quicksort

Loading...

Similar Threads - Stack Overflow Quicksort | Date |
---|---|

C/++/# Don't understand tower of Hanoi Program Stack | Feb 10, 2017 |

Fortran Integer overflow on assignment | Dec 26, 2016 |

C/++/# Question about learning C++ Linked Lists before Stacks... | Oct 6, 2016 |

Create a custom stack class with a swap method? | Dec 20, 2015 |

Stack struct function | Mar 7, 2015 |

**Physics Forums - The Fusion of Science and Community**