Как ревертировать эту рутину, чтобы избежать использования рекурсии?

Question

Так что я писал Сортировка слиянием в C # как а упражнение И хотя он работал, оглядываясь назад на код, там была место для улучшения.

В основном вторая часть алгоритма требует рутины к объединить два отсортированных списка.

Вот мой путь слишком длинный реализация, которая может использовать рефакторинг:

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    if (sLeft.Count == 0 || sRight.Count == 0)
    {
        sLeft.AddRange(sRight);
        return sLeft;
    }
    else if (sLeft.Count == 1 && sRight.Count == 1)
    {
        if (sLeft[0] <= sRight[0])
            sLeft.Add(sRight[0]);
        else
            sLeft.Insert(0, sRight[0]);
        return sLeft;
    }
    else if (sLeft.Count == 1 && sRight.Count > 1)
    {
        for (int i=0; i<sRight.Count; i++)
        {
            if (sLeft[0] <= sRight[i])
            {
                sRight.Insert(i, sLeft[0]);
                return sRight;
            }
        }
        sRight.Add(sLeft[0]);
        return sRight;
    }
    else if (sLeft.Count > 1 && sRight.Count == 1)
    {
        for (int i=0; i<sLeft.Count; i++)
        {
            if (sRight[0] <= sLeft[i])
            {
                sLeft.Insert(i, sRight[0]);
                return sLeft;
            }
        }
        sLeft.Add(sRight[0]);
        return sLeft;
    }
    else
    {
        List<int> list = new List<int>();
        if (sLeft[0] <= sRight[0])
        {
            list.Add(sLeft[0]);
            sLeft.RemoveAt(0);
        }
        else
        {
            list.Add(sRight[0]);
            sRight.RemoveAt(0);
        }

        list.AddRange(MergeSortedLists(sLeft, sRight));
        return list;
    }       
}

Конечно, эта рутина может быть улучшена / сокращена путем удаления рекурсия, И т. Д. Есть даже другие способы объединения 2 отсортированных списка. Так Любые рефакторинг приветствуется.

Хотя у меня есть ответ, мне интересно, как бы другие программисты могли бы улучшить эту рутину.

Спасибо!

Answer 1

В качестве отправной точки я бы удалил ваши особые случаи, когда любой из списков имеет Count == 1 - Они могут быть обработаны вашим более общим (в настоящее время рекурсирующим) случай.

То if (sLeft.Count > 1 && sRight.Count == 0) буду никогда быть правдой, потому что вы проверили на sRight.Count == 0 В начале - так что этот код никогда не будет достигнут и является избыточным.

Наконец, вместо того, чтобы речь (который очень дорого в этом случае из-за количества новых списков, которые вы создаете - один из элементов!), Я бы сделал что-то вроде этого в вашем else (На самом деле это может заменить весь ваш метод):

List<int> list = new List<int>();

while (sLeft.Count > 0 && sRight.Count > 0)
{
    if (sLeft[0] <= sRight[0])
    {
        list.Add(sLeft[0]);
        sLeft.RemoveAt(0);
    }
    else
    {
        list.Add(sRight[0]);
        sRight.RemoveAt(0);
    }
}

// one of these two is already empty; the other is in sorted order...
list.AddRange(sLeft);
list.AddRange(sRight);
return list;

(В идеале я рефикторую это использовать целочисленные индексы против каждого списка, а не использовать .RemoveAt, Поскольку это больше исполнителю для петли через список, чем уничтожить его, и потому, что может быть полезно оставить оригинальные списки Intact. Это все еще более эффективный код, чем оригинал, хотя!)

Answer 2

Объединение двух сортировков можно сделать в O (n).

List<int> lList, rList, resultList;
int r,l = 0;

while(l < lList.Count && r < rList.Count)
{
  if(lList[l] < rList[r]
    resultList.Add(lList[l++]);
  else
    resultList.Add(rList[r++]);
}
//And add the missing parts.
while(l < lList.Count)
  resultList.Add(lList[l++]);
while(r < rList.Count)
  resultList.Add(rList[r++]);

Answer 3

Мой взять на это было бы:

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    List<int> result = new List<int>();
    int indexLeft = 0;
    int indexRight = 0;

    while (indexLeft < sLeft.Count || indexRight < sRight.Count)
    {
        if (indexRight == sRight.Count ||
            (indexLeft < sLeft.Count && sLeft[indexLeft] < sRight[indexRight]))
        {
            result.Add(sLeft[indexLeft]);
            indexLeft++;
        }
        else
        {
            result.Add(sRight[indexRight]);
            indexRight++;
        }
    }
    return result;
}

Именно то, что я бы сделал, если бы мне пришлось сделать это вручную. знак равно

Answer 4

Вы действительно уверены, что ваш код вообще работает? Без тестирования я вижу следующее:

...
else if (sLeft.Count > 1 && sRight.Count == 0)  //<-- sRight is empty
{
    for (int i=0; i<sLeft.Count; i++)
    {
        if (sRight[0] <= sLeft[i]) //<-- IndexError?
        {
            sLeft.Insert(i, sRight[0]);
            return sLeft;
        }
    }
    sLeft.Add(sRight[0]);
    return sLeft;
}
...

Answer 5

Вы также просили разные подходы. Я мог бы сделать как ниже в зависимости от использования. Код ниже ленивый, поэтому он не будет сортировать весь список одновременно, но только при запросе элементов.

class MergeEnumerable<T> : IEnumerable<T>
    {
        public IEnumerator<T> GetEnumerator()
        {
            var left = _left.GetEnumerator();
            var right = _right.GetEnumerator();
            var leftHasSome = left.MoveNext();
            var rightHasSome = right.MoveNext();
            while (leftHasSome || rightHasSome)
            {
                if (leftHasSome && rightHasSome)
                {
                  if(_comparer.Compare(left.Current,right.Current) < 0)
                  {
                    yield return returner(left);
                  } else {
                    yield return returner(right);
                  }
                }
                else if (rightHasSome)
                {
                    returner(right);
                }
                else
                {
                    returner(left);
                }
            }
        }

        private T returner(IEnumerator<T> enumerator)
        {
            var current = enumerator.Current;
            enumerator.MoveNext();
            return current;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)this).GetEnumerator();
        }

        private IEnumerable<T> _left;
        private IEnumerable<T> _right;
        private IComparer<T> _comparer;

        MergeEnumerable(IEnumerable<T> left, IEnumerable<T> right, IComparer<T> comparer)
        {
            _left = left;
            _right = right;
            _comparer = comparer;
        }
    }

РЕДАКТИРОВАТЬ: В основном то же самое реализация, что и Сергей Осипчук, его воля от начала добиваться, когда смотрите только на сортировку, будь самым быстрым, но задержка будет выше, а также будет выше факта сортировки всего списка аванс. Так как я сказал, в зависимости от использования, я мог бы пойти с этим подходом, и альтернатива будет чем-то похожем на Сергею Осипчук

Answer 6

Часто вы можете использовать стек вместо использования рекурсии

Answer 7

Список слияния (по теории, списки ввода сортируются заранее) сортировка может быть реализована следующим образом:

List<int> MergeSorting(List<int> a, List<int> b)
    {
        int apos = 0;
        int bpos = 0;
        List<int> result = new List<int>();
        while (apos < a.Count && bpos < b.Count)
        {
            int avalue = int.MaxValue;
            int bvalue = int.MaxValue;
            if (apos < a.Count)
                avalue = a[apos];
            if (bpos < b.Count)
                bvalue = b[bpos];
            if (avalue < bvalue)
            {
                result.Add(avalue);
                apos++;
            }
            else
            {
                result.Add(bvalue);
                bpos++;
            }
        }
        return result;
    }

В случае, если вы начнете с не отсортированного списка, вам нужно разделить его путем отсортированной подпоследовательности, а затем MGGE их используя функцию выше

Answer 8

Я никогда не пользуюсь рекурсией для слияния. Вы можете сделать итеративные пропускания по входу, используя тот факт, что размер отсортированного блока удваивается с каждым пройденным слиянием. Следите за размером блока и подсчетом элементов, которые вы обработаны из каждого списка ввода; Когда они равны, список исчерпан. Когда оба списка исчерпаны, вы можете перейти к следующей паре блоков. Когда размер блока больше или равен вашему размеру ввода, вы закончите.

Редактировать: Некоторые из информации, которую я оставил ранее, был неверной, из-за моего недоразумения - список в C # аналогичен массиву, а не связанным списком. Мои извенения.