C# quicksort funcional está fallando

Question

Estoy tratando de implementar quicksort en un estilo funcional usando C# utilizando linq, y este código funciona al azar/no funciona, y no puedo entender por qué.
Importante mencionar: Cuando llamo esto a una matriz o lista, funciona bien. Pero en un desconocido-lo-que-realmente-se IEnumerable, que se vuelve loco (pierde los valores o se bloquea, por lo general funciona a veces..)
El código:

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; 
    } 

¿Se puede encontrar fallos aquí eso causaría que esto fallara?

Editar: Algunos mejor código de prueba:

 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

Algunos casos enumerables, como los devueltos por LINQ a las consultas SQL o Entity Framework, sólo está concebida para ser iterado vez. Su código requiere múltiples iteraciones y se bloqueará o se comportará de manera extraña en este tipo de instancias. Tendría que materializar esos enumerables con ToArray() o un método similar primero.

También debería reutilizar ese pivot para que no tenga que seguir iterando para el primer elemento y los restantes. Esto no puede resolver completamente el problema, sino que va a ayudar en algunos casos: (. También no es necesario que iterar a través de lasortedQuery - simplemente devolverlo, ya que es 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()); 
} 

En una nota relacionada, ¿por qué siente la necesidad de volver a implementar esta funcionalidad? Enumerable.OrderBy ya lo hace por ti.

---

de respuesta a la actualización:

Sus pruebas están fallando debido a su prueba está mal, no es el algoritmo.

Random es una fuente de entrada no determinista y, como he explicado anteriormente, el método de clasificación necesita realizar múltiples iteraciones en la misma secuencia. Si la secuencia es totalmente aleatoria, obtendrá diferentes valores en iteraciones posteriores. Básicamente, estás tratando de ordenar una secuencia cuyos elementos cambian constantemente.

Si quiere que la prueba sea exitosa, necesita hacer la entrada consistente. Utilice una semillapara el generador de números aleatorios:

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

continuación:

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(); 
} 

Se va a volver a ordenar.