9

I'm trying to implement quicksort in a functional style using C# using linq, and this code randomly works/doesn't work, and I can't figure out why.
Important to mention: When I call this on an array or list, it works fine. But on an unknown-what-it-really-is IEnumerable, it goes insane (loses values or crashes, usually. sometimes works.)
The 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;
    }

Can you find any faults here that would cause this to fail?

Edit: Some better test code:

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

1 回答 1

7

一些可枚举的实例，例如由 Linq 返回的 SQL 或实体框架查询，仅设计为迭代一次。您的代码需要多次迭代，并且会在这些类型的实例上崩溃或表现异常。您必须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是一个不确定的输入源，正如我上面解释的，排序方法需要在同一个序列上执行多次迭代。如果序列是完全随机的，那么它将在后续迭代中得到不同的值。本质上，您是在尝试对元素不断变化的序列进行快速排序！

如果你想让测试成功，你需要使输入一致。使用随机数生成器的种子：

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

它会回来排序。

于 2010-04-24T14:37:45.800 回答