C # quicksort funzionale sta fallendo

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 menzionare: Quando chiamo questo su un array o lista, funziona benissimo. 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 potrebbe causare questo a fallire?

Modifica 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 comportarsi in modo strano su questi tipi di casi. Dovreste materializzarsi quelle enumerables con ToArray() o un metodo simile prima.

Si dovrebbe anche essere il riutilizzo che pivot in modo che non c'è bisogno di tenere l'iterazione per il primo e elementi rimanenti. Questo non può risolvere completamente il problema, ma sarà aiutare in alcuni casi:

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

(È inoltre non è necessario iterate attraverso il sortedQuery -. Basta restituirlo, è già un IEnumerable<T>)

In una nota correlata, il motivo per cui si sente il bisogno di ri-implementare questa funzionalità? Enumerable.OrderBy già fa per voi.

---

Response to update:

I tuoi test non riescono, perché il test è sbagliato , non l'algoritmo.

Random è una sorgente di ingresso non-deterministico, come spiegato sopra, le esigenze metodo di ordinamento per eseguire più iterazioni sulla stessa sequenza. Se la sequenza è del tutto casuale, allora sta per arrivare su valori diversi iterazioni successive. In sostanza, si sta cercando di Quicksort una sequenza i cui elementi continuare a cambiare!

Se si desidera che il test per avere successo, è necessario effettuare l'ingresso 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();
    }
}

Quindi:

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.