Quicksort causes stackoverflow
-
21-09-2019 - |
Question
I have the following code, (taken from here), but it causes a stackoverflow exception when there's two the same value's in the list to sort.
Can someone help me what's causing this?
public static IEnumerable<int> QSLinq(IEnumerable<int> _items)
{
if (_items.Count() <= 1)
return _items;
var _pivot = _items.First();
var _less = from _item in _items where _item < _pivot select _item;
var _same = from _item in _items where _item == _pivot select _item;
var _greater = from _item in _items where _item > _pivot select _item;
return QSLinq(_less).Concat(QSLinq(_same)).Concat(QSLinq(_greater));
}
Solution
You shouldn't be making a recursive call to sort _same
- you know it's sorted, since all the values are the same!
OTHER TIPS
But not complete: selecting the first element as pivot and not sorting the smallest subarray first will also overflow your stack.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow