Un autre stackoverflow Quicksort

Question

J'ai donc essayé d'implémenter moi-même un quicksort, juste pour en apprendre quelque chose, mais il génère aussi une exception stackoverflow, mais je n'arrive pas à trouver la cause.

Quelqu'un peut-il me donner un indice?

public void Partition(List<int> valuelist, out List<int> greater, out List<int> lesser) 
     { 
      lesser = new List<int>(); // <-- Stackoverflow exception here! 
      greater = new List<int>(); 

      if (valuelist.Count <= 1) 
       return; 

      pivot = valuelist.First(); 

      foreach (int Element in valuelist) 
      { 
       if (Element <= pivot) 
        lesser.Add(Element); 
       else 
        greater.Add(Element); 
      } 
     } 

     public List<int> DoQuickSort(List<int> list) 
     { 
      List<int> great; 
      List<int> less; 

      Partition(list, out great, out less); 

      DoQuickSort(great); 
      DoQuickSort(less); 

      list.Clear(); 
      list = (List<int>)less.Concat(great); 

      return list; 

     } 

Answer 1

Vous n'êtes pas mettre des conditions sur vos appels récursifs à DoQuicksort, il ne cesserai jamais récursion, conduisant à un débordement de pile. Vous ne devez appeler le DoQuicksort que s'il contient plus d'un élément.

Editer: Comme il l'a dit dans son commentaire, il s'agit d'une approche très lente de "Quicksort". Vous devriez regarder les algorithmes de partitionnement sur place, comme mentionné sur le Quicksort article de Wikipedia.

Answer 2

vous faites une boucle infinie là

DoQuickSort(great); 

vous avez besoin d'un moyen de sortir de cette boucle avec un drapeau ou une condition

Modifier
J'ajouterai qu'en mode de débogage, avec le paramètre par défaut, vous ne pouvez atteindre que entre 10 000 et 16 000 appels récursifs avant qu'une exception soit lancée et entre 50 000 et 80 000 en mode de libération, tous dépendent de le code réel exécuté.

Si vous jouez avec un grand nombre de valeurs, vous devrez peut-être gérer vous-même cet appel récursif en utilisant un objet Stack.

exemple de code pour voir combien appelez avant qu'il ne se bloque;
(debug, 14210 appel, la libération 80071 appel)

static int s = 1; 
    static void Main(string[] args) 
    { 
     o(); 
    } 

    static void o() 
    { 
     s++; 
     Console.WriteLine(s.ToString()); 
     o(); 
    } 

Answer 3

Je pense que l'un des problèmes dans votre code que vous gardez la valeur de pivot lors du partitionnement de la liste. Cela signifie que vous rencontrerez une situation où toutes les valeurs seront plus ou moins partagées, et le partitionnement cessera de fonctionner. Cela ne vous permettra en réalité plus de diviser une des listes, donc la condition de sortie dans la méthode Partition n'est jamais satisfaite.

Vous devez sélectionner une valeur pivot, retirer l'élément pivot de la liste (cette partie est manquante dans votre code), parition en plus et moins listes, trier les (récursive), puis concaténer moins la liste , l'élément pivot (il manque naturellement aussi dans votre code) et la plus grande liste.

Je peux poster une mise à jour, de travail, exemple de code, mais puisque vous êtes en mode « apprentissage », je vais le garder pour moi jusqu'à ce que vous le demander :)