Recursive QuickSort suffering from StackOverflowException
I am working on implementing the recursive QuickSort method in the GenericList class. I will have a second method that takes compareDelegate to compare different types, but for development purposes I am sorting GenericList < int
>.
I am getting stackoverflow areas in different places depending on the size of the list.
I've been looking and tracing this code for hours and probably just needed new pairs of (more experienced) eyes. I definitely want to know why it is broken, not just how to fix it.
public void QuickSort()
{
int i, j, lowPos, highPos, pivot;
GenericList<T> leftList = new GenericList<T>();
GenericList<T> rightList = new GenericList<T>();
GenericList<T> tempList = new GenericList<T>();
lowPos = 1; highPos = this.Count;
if (lowPos < highPos)
{
pivot = lowPos;
for (i = 2; i <= highPos; i++)
{
if (this[i].CompareTo(this[pivot]) <= 0)
leftList.Add(this[i]);
else
rightList.Add(this[i]);
}
leftList.Add(this[pivot]);
leftList.QuickSort();
rightList.QuickSort();
for(i=1;i<=leftList.Count;i++)
tempList.Add(leftList[i]);
for(i=1;i<=rightList.Count;i++)
tempList.Add(rightList[i]);
this.items = tempList.items;
this.count = tempList.count;
}
}
Finished product:
public void QuickSort()
{
Random random = new Random();
int i, j, lowPos, highPos, pivot;
GenericList<T> leftList = new GenericList<T>();
GenericList<T> rightList = new GenericList<T>();
GenericList<T> tempList = new GenericList<T>();
if (this.Count > 1)
{
pivot = random.Next(1,this.Count);
for (i = 1; i <= this.Count; i++)
{
if (i == pivot) continue;
if (this[i].CompareTo(this[pivot]) < 0)
leftList.Add(this[i]);
else
rightList.Add(this[i]);
}
leftList.QuickSort();
rightList.QuickSort();
for(i=1;i<=leftList.Count;i++)
tempList.Add(leftList[i]);
tempList.Add(this[pivot]);
for(i=1;i<=rightList.Count;i++)
tempList.Add(rightList[i]);
this.items = tempList.items;
this.count = tempList.count;
}
}
a source to share
Your implementation includes a summary in your sublist. By including the pivot point in your sublists (in this case your left-hand list because your condition is <=), you are setting yourself up for possible infinite recursion if that point is in the middle of the sublists.
Example:
- List = [3, 6, 12 , 4, 8] Pivot = 3 ( 12 ) Left = [3, 6, 12 >, 4, 8] Right = [Empty]
- List = [3, 6, 12 , 4, 8] Pivot = 3 ( 12 ) Left = [3, 6, 12 >, 4, 8] Right = [Empty]
- List = [3, 6, 12 , 4, 8] Pivot = 3 ( 12 ) Left = [3, 6, 12 >, 4, 8] Right = [Empty]
- ... Infinite loop
Since the pivot is not eliminated (although its end position is known), this can cause you to sort the same list over and over, rather than reducing the size of the lists to sort with each recursive call.
If you exclude your vault (by index, not by value) from the subscriptions and add it back to the last tempList between leftList and rightList, it works correctly.
...
for (i = 1; i <= highPos; i++)
{
if (i == pivot) continue; // Add this
if (this[i].CompareTo(this[pivot]) <= 0)
...
for (i = 1; i <= leftList.Count; i++)
tempList.Add(leftList[i]);
tempList.Add(this[pivot]); // Add this
for (i = 1; i <= rightList.Count; i++)
tempList.Add(rightList[i]);
...
See also: Wikipedia article on Quicksort (with pseudocode)
a source to share
You can get some insight from this blog series:
http://reprog.wordpress.com/2010/04/25/writing-correct-code-part-1-invariants-binary-search-part-4a/
When you're done with that, trace your code in your mind with the input set {1, 2} and tell me what the result will be.
a source to share
I would not recommend putting the rod in one of the two groups. If you only have two elements that are equal, you can end up with an infinite loop. For example, if you try to sort the array {1,1}, you should end up with an infinite loop that could cause it. Most quicksorts avoid this by replacing the hinge with an element with an edge and then sorting the rest of the array. Another way to deal with this would be to put in a string to make sure you don't add a pivot point to the left like
if(i != pivot)
Then you added a pivot to the tempList between adding the leftList and adding the rightList.
Edit:
Nick is right that you get the problem for other cases like {5,2}. However, even if you fix the current problem by not putting the pivot in the list to be sorted again, you might want to make sure that your code can handle duplicate items. A large array of the same number will give you O (N ^ 2) time complexity, and if N is large enough then you will get a stack overflow.
a source to share
See what happens when you have a List
containing [5,2].
. Yours pivot
will be equal 1
, so the value used for comparison will be 5
. The string this[i].CompareTo(this[pivot]) <= 0
will be True
, and the number 5
will be placed in leftList
. The next comparison with 2
will also be True
by placing 2
in leftList
. Now yours leftList
will be exactly where it started: [5,2]
which you will be calling QuickSort
over and over ... and it will exit exactly like the nausem: StackOverflow declaration.
a source to share