Изучение LINQ: QuickSort

Как насчет этого? (Если я хорошо понимаю, вам не нравятся вызовы .ToList)

public static IEnumerable<int> QSLinq(IEnumerable<int> items)
{
    if (items.Count() <= 1)
        return items;

    int pivot = items.First();

    return QSLinq(items.Where(i => i < pivot))
        .Concat(items.Where(i => i == pivot))
        .Concat(QSLinq(items.Where(i => i > pivot)));
}

Отказ от ответственности на основании Джон ответ: НЕ используйте этот алгоритм в реальной проблеме. Это очень неэффективно.

Все задействовано в кастинге? Я не вижу кастингов. То, что я вижу делать, - это вызовы ToList, которые ужасно неэффективны. В основном LINQ предназначен для работы с последовательностями, которые по сути не позволяют вам работать на месте (или в дублированном пространстве) так, как это обычно делается при быстрой сортировке. По сути, здесь происходит очень много копирования данных :(

Просто измените тип параметра на IEnumerable и используйте конструкцию var вместо List<int> для ваших локальных переменных.

Это улучшит ваш метод QSLinq, поскольку он будет принимать больше типов параметров, например int[], а также List<int>.

Смотрите новый метод:

    public static IEnumerable<int> QSLinq(IEnumerable<int> _items)
    {
        if (_items.Count() <= 1)
            return _items;

        var _pivot = _items.First();

        var _less = from _item in _items where _item < _pivot select _item;
        var _same = from _item in _items where _item == _pivot select _item;
        var _greater = from _item in _items where _item > _pivot select _item;

        return QSLinq(_less).Concat(QSLinq(_same)).Concat(QSLinq(_greater));
    }

Надеюсь это поможет.

Интересный вопрос! Это не превосходит OrderBy, но несколько ограничивает повторные перечисления.

    public static IEnumerable<int> QSort2(IEnumerable<int> source)
    {
        if (!source.Any())
            return source;
        int first = source.First();
        return source
            .GroupBy(i => i.CompareTo(first))
            .OrderBy(g => g.Key)
            .SelectMany(g => g.Key == 0 ? g : QSort2(g));
    }

Я случайно сгенерировал stackoverflow во время разработки, так как QSorted, когда Key == 0.

Ради интереса я протестировал эти решения. Я совершил кардинальный грех тестирования производительности (тестирование в режиме отладки), но я не думаю, что это повлияет на большой эффект O, который мы увидим. Вот ввод (обратный ввод - худший случай для быстрой сортировки)

IEnumerable<int> source = Enumerable.Range(0, 1000).Reverse().ToList();

• Решение тройного concat-where заняло 71000 миллисекунд.
• Мое решение заняло 330 миллисекунд
• OrderBy.ToArray занял 15 миллисекунд (разрешение таймера, поэтому фактическое время, вероятно, меньше)

Вот еще одно решение с использованием Aggregate. Я называю это: Группируйся и лови рыбу. Это занимает 170 мс в моем тесте на 1000 обратных элементов.

    public static IEnumerable<int> QSort3(IEnumerable<int> source)
    {
        if (!source.Any())
            return source;
        int first = source.First();

        QSort3Helper myHelper = 
          source.GroupBy(i => i.CompareTo(first))
          .Aggregate(new QSort3Helper(), (a, g) =>
              {
                  if (g.Key == 0)
                      a.Same = g;
                  else if (g.Key == -1)
                      a.Less = g;
                  else if (g.Key == 1)
                      a.More = g;
                  return a;
              });
        IEnumerable<int> myResult = Enumerable.Empty<int>();
        if (myHelper.Less != null)
            myResult = myResult.Concat(QSort3(myHelper.Less));
        if (myHelper.Same != null)
            myResult = myResult.Concat(myHelper.Same);
        if (myHelper.More != null)
            myResult = myResult.Concat(QSort3(myHelper.More));

        return myResult;
    }

    public class QSort3Helper
    {
        public IEnumerable<int> Less;
        public IEnumerable<int> Same;
        public IEnumerable<int> More;
    }

Почему это быстрее, чем мое решение, использующее OrderBy? Я думаю, это немного более устойчиво к худшему случаю.

Выбранный ответ неверен, потому что он включает QSLinq (_same) вместо просто _same в возвращаемой коллекции и приводит к исключению StackOverflowException. Я буду использовать фиксированную версию в качестве контроля. Если решение может использовать копирование, скорость можно резко увеличить. Использование потоков вместо параллельного на самом деле немного снижает производительность при копировании вариантов. Использование потоков для вариантов без копирования немного увеличивает производительность. Отличие параллельной и некопирующей производительности от контроля незначительное.

самое быстрое копирование:

private static List<int> quickie7(List<int> ites)
{
    if (ites.Count <= 1)
        return ites;
    var piv = ites[0];
    List<int> les = new List<int>();
    List<int> sam = new List<int>();
    List<int> mor = new List<int>();
    Enumerable.Range(0, 3).AsParallel().ForAll(i =>
    {
        switch (i)
        {
            case 0: les = (from _item in ites where _item < piv select _item).ToList(); break;
            case 1: sam = (from _item in ites where _item == piv select _item).ToList(); break;
            case 2: mor = (from _item in ites where _item > piv select _item).ToList(); break;
        }
    });
    var _les = new List<int>();
    var _mor = new List<int>();
    Enumerable.Range(0, 2).AsParallel().ForAll(i =>
    {
        switch (i)
        {
            case 0: _les = quickie7(les); break;
            case 1: _mor = quickie7(mor); break;
        }
    });
    List<int> allofem = new List<int>();
    allofem.AddRange(_les);
    allofem.AddRange(sam);
    allofem.AddRange(_mor);
    return allofem;
}

самый быстрый без копирования:

public static IEnumerable<int> QSLinq3(IEnumerable<int> _items)
{
    if (_items.Count() <= 1)
        return _items;
    var _pivot = _items.First();
    IEnumerable<int> _less = null;
    IEnumerable<int> _same = null;
    IEnumerable<int> _greater = null;
    ConcurrentBag<ManualResetEvent> finishes = new ConcurrentBag<ManualResetEvent>();
    Enumerable.Range(0, 3).AsParallel().ForAll(i =>
    {
        var fin = new ManualResetEvent(false);
        finishes.Add(fin);
        (new Thread(new ThreadStart(() =>
        {
            if (i == 0)
                _less = from _item in _items where _item < _pivot select _item;
            else if (i == 1)
                _same = from _item in _items where _item == _pivot select _item;
            else if (i == 2)
                _greater = from _item in _items where _item > _pivot select _item;
            fin.Set();
        }))).Start();
    });
    finishes.ToList().ForEach(k => k.WaitOne());
    return QSLinq(_less).Concat(_same).Concat(QSLinq(_greater));
}