This is a weired problem, I have implemented simple quick sort as follows..
static void Main(string[] args)
{
List<int> unsorted = new List<int> { 1, 3, 5, 7, 9, 8, 6, 4, 2 };
List<int> sorted = quicksort(unsorted);
Console.WriteLine(string.Join(",", sorted));
Console.ReadKey();
}
private static List<T> quicksort<T>(List<T> arr) where T : IComparable<T>
{
List<T> loe = new List<T>(), gt = new List<T>();
if (arr.Count < 2)
return arr;
int pivot = arr.Count / 2;
T pivot_val = arr[pivot];
arr.RemoveAt(pivot);
foreach (T i in arr)
{
if (i.CompareTo(pivot_val) <= 0)
loe.Add(i);
else
gt.Add(i);
}
List<T> resultSet = new List<T>();
resultSet.AddRange(quicksort(loe));
gt.Add(pivot_val);
resultSet.AddRange(quicksort(gt));
return resultSet;
}
Output is : 1,2,3,4,5,6,7,8,9
But When I use any negative number in the unsorted list there is a stackoverflow error,
for example if List unsorted = new List { 1, 3, 5, 7, 9, 8, 6, 4, 2, -1 }; Now there is a stackoverflow..
What's going on? Why this is not working ?
Your algorithm has a bug. Consider the simplest input list { 1, -1 }. Let's step through your logic.
arr
list.arr
list (there's just the 1 at index 0) with the pivot.gt
list.loe
list, which is empty. That sort returns an empty list, which you add to the result set.gt
list, so the gt
list now looks like this: { 1, -1 }. Notice that this is the exact same list as you started with.gt
list. Since you are calling the quicksort routine with the same input, the same sequence of steps happens again, until the stack overflows.It seems the error in your logic is that you blindly add the pivot to the gt list without comparing it to anything. I'll leave it to you to figure out how to make it work.
Edited to add: I'm assuming this is a homework assignment, but if it's not, I would highly recommend using .NET's built in Sort()
method on List<T>
. It has been highly optimized and heavily tested, and will most likely perform better than anything home-brewed. Why reinvent the wheel?