Le quicksort fonctionnel C# échoue

Question

J'essaie d'implémenter le quicksort dans un style fonctionnel en utilisant C# en utilisant linq, et ce code fonctionne aléatoirement/ne fonctionne pas, et je ne peux pas comprendre pourquoi.
Important à mentionner: Lorsque je l'appelle sur un tableau ou une liste, cela fonctionne très bien. Mais sur un inconnu-ce-it-vraiment-est IEnumerable, il devient fou (perd des valeurs ou des accidents, en général fonctionne parfois..)
Le code:

public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source) 
     where T : IComparable<T> 
    { 
     if (!source.Any()) 
      yield break; 
     var pivot = source.First(); 
     var sortedQuery = source.Skip(1).Where(a => a.CompareTo(source.First()) <= 0).Quicksort() 
          .Concat(new[] { pivot }) 
          .Concat(source.Skip(1).Where(a => a.CompareTo(source.First()) > 0).Quicksort()); 
     foreach (T key in sortedQuery) 
      yield return key; 
    } 

Pouvez-vous trouver des défauts ici cela ferait échouer cela?

Edit: Certains meilleur code de test:

 var rand = new Random(); 
     var ienum = Enumerable.Range(1, 100).Select(a => rand.Next()); 
     var array = ienum.ToArray(); 
     try 
     { 
      array.Quicksort().Count(); 
      Console.WriteLine("Array went fine."); 
     } 
     catch (Exception ex) 
     { 
      Console.WriteLine("Array did not go fine ({0}).", ex.Message); 
     } 
     try 
     { 
      ienum.Quicksort().Count(); 
      Console.WriteLine("IEnumerable went fine."); 
     } 
     catch (Exception ex) 
     { 
      Console.WriteLine("IEnumerable did not go fine ({0}).", ex.Message); 
     } 

Answer 1

Quelques cas dénombrables, tels que ceux qui sont renvoyés par les requêtes LINQ to SQL ou Entity Framework, ne sont conçus pour être itéré fois. Votre code nécessite plusieurs itérations et se bloque ou se comporte étrangement sur ces types d'instances. Vous devez matérialiser ces énumération avec ToArray() ou une méthode similaire en premier.

Vous devriez également réutiliser ce pivot de sorte que vous n'ayez pas à conserver l'itération pour les éléments premiers et restants. Cela peut ne pas résoudre complètement le problème, mais ça va aider dans certains cas: (. Vous ne avez pas besoin de itérer par la sortedQuery - il suffit de retourner, il est déjà un IEnumerable<T>)

public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source) 
    where T : IComparable<T> 
{ 
    if (!source.Any()) 
     return source; 
    var pivot = source.First(); 
    var remaining = source.Skip(1); 
    return remaining 
     .Where(a => a.CompareTo(pivot) <= 0).Quicksort() 
     .Concat(new[] { pivot }) 
     .Concat(remaining.Where(a => a.CompareTo(pivot) > 0).Quicksort()); 
} 

Sur une note connexe, pourquoi ressentez-vous le besoin de ré-implémenter cette fonctionnalité? Enumerable.OrderBy le fait déjà pour vous.

---

Réponse à jour:

vos tests échouent parce que votre test est erroné, pas l'algorithme.

Random est une source d'entrée non déterministe et, comme je l'ai expliqué ci-dessus, la méthode de tri doit effectuer plusieurs itérations sur la même séquence. Si la séquence est totalement aléatoire, elle aura des valeurs différentes sur les itérations suivantes. Essentiellement, vous essayez de faire une séquence rapide dont les éléments ne cessent de changer!

Si vous souhaitez que le test réussisse, vous devez rendre l'entrée cohérente. Utilisez une graines pour le générateur de nombres aléatoires:

static IEnumerable<int> GetRandomInput(int seed, int length) 
{ 
    Random rand = new Random(seed); 
    for (int i = 0; i < length; i++) 
    { 
     yield return rand.Next(); 
    } 
} 

Puis:

static void Main(string[] args) 
{ 
    var sequence = GetRandomInput(248917, 100); 
    int lastNum = 0; 
    bool isSorted = true; 
    foreach (int num in sequence.Quicksort()) 
    { 
     if (num < lastNum) 
     { 
      isSorted = false; 
      break; 
     } 
     lastNum = num; 
    } 
    Console.WriteLine(isSorted ? "Sorted" : "Not sorted"); 
    Console.ReadLine(); 
} 

Il reviendra triés.