Quicksort provoque stackoverflow
-
21-09-2019 - |
Question
Je le code suivant, (pris ici), mais il provoque une exception StackOverflow quand il y a deux de la même valeur dans la liste pour trier.
Quelqu'un peut-il me aider ce qui cause?
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));
}
La solution
Vous ne devrait pas faire un appel récursif à trier _same
- vous le savez est triée, puisque toutes les valeurs sont les mêmes
Autres conseils
Mais pas complète. Sélectionner le premier élément de pivot et non de tri le plus petit sous-tableau premier débordera également votre pile
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow