C# quicksort funzionale sta venendo a mancare

Question

Sto cercando di attuare Quicksort in uno stile funzionale utilizzando C# utilizzando LINQ, e questo codice funziona in modo casuale/non funziona, e non riesco a capire perché.
Importante ricordare: quando lo chiamo su un array o un elenco, funziona correttamente. Ma su una sconosciuta-ciò-che-davvero-è IEnumerable, si impazzisce (perde valori o si blocca, di solito a volte funziona..)
Il codice:

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

si può trovare alcun difetto qui che farebbe fallire questo?

Edit: Alcuni codice di prova migliore:

 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

alcuni casi enumerabili, come quelli restituiti da LINQ to SQL o query Entity Framework, sono progettati solo per essere iterata una volta. Il tuo codice richiede più iterazioni e si blocca o si comporta in modo strano su questi tipi di istanze. Dovresti materializzare quelle enumerables con ToArray() o un metodo simile prima.

Si dovrebbe anche riutilizzare il numero pivot in modo da non dover continuare a ripetere per il primo e gli altri elementi. Questo non può risolvere completamente il problema, ma sarà aiutare in alcuni casi: (. Inoltre, non c'è bisogno di iterate attraverso il sortedQuery - basta restituirlo, è già 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()); 
} 

Su una nota correlata, perché senti la necessità di ri-implementare questa funzionalità? Enumerable.OrderBy lo fa già per te.

---

Risposta per aggiornare:

i test stanno fallendo perché il test è sbagliato, non l'algoritmo.

Random è una sorgente di input non deterministica e, come ho spiegato sopra, il metodo di ordinamento deve eseguire più iterazioni sulla stessa sequenza. Se la sequenza è totalmente casuale, otterrà valori diversi nelle iterazioni successive. In sostanza, stai provando a eseguire una successione rapida di una sequenza i cui elementi continuano a cambiare!

Se si desidera che il test abbia esito positivo, è necessario rendere coerente coerente. Utilizzare un seme per il generatore di numeri casuali:

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

Poi:

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

Si tornerà ordinato.