Сбой функциональной быстрой сортировки C #

Question

Я пытаюсь реализовать быструю сортировку в функциональном стиле, используя C #, используя linq, и этот код случайным образом работает / не работает, и я не могу понять, почему.
Важно упомянуть: когда я вызываю это в массив или список, он работает нормально. Но на неизвестном, что это на самом деле IEnumerable, он сходит с ума (теряет значения или падает, обычно. Иногда работает.)
Код:

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

Можете ли вы найти здесь какие-либо неисправности, которые могут привести к сбою?

Редактировать: Некоторый лучший тестовый код:

        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

Некоторые перечисляемые экземпляры, такие как возвращаемые запросами Linq к SQL или Entity Framework, предназначены для повторения только один раз. Ваш код требует многократных итераций и будет зависать или вести себя странно на таких типах экземпляров. Вы должны были бы материализовать эти перечислимые значения сначала с помощью ToArray() или аналогичного метода.

Вам также следует повторно использовать pivot, чтобы вам не приходилось повторять итерации для первого и оставшихся элементов. Это может не полностью решить проблему, но в некоторых случаях это поможет:

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

(Вам также не нужно повторять через sortedQuery - просто верните его, это уже IEnumerable<T>.)

В связанной заметке, почему вы чувствуете необходимость повторно реализовать эту функцию? Enumerable.OrderBy уже делает это для вас.

---

Ответ на обновление:

Ваши тесты не пройдены, потому что ваш тест неправильный , а не алгоритм.

Random - это недетерминированный входной источник, и, как я объяснил выше, метод сортировки должен выполнять несколько итераций в одной и той же последовательности. Если последовательность абсолютно случайна, то на последующих итерациях она получит разные значения. По сути, вы пытаетесь быстро отсортировать последовательность, элементы которой постоянно меняются!

Если вы хотите, чтобы тест прошел успешно, вы должны сделать ввод непротиворечивым . Используйте seed для генератора случайных чисел:

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

Тогда:

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

Вернется отсортированным.