Очередной стековый поток Quicksort - PullRequest
Новая
       15

Очередной стековый поток Quicksort

2 голосов
/ 19 января 2010

Итак, я сам пытался реализовать быструю сортировку, просто чтобы чему-то научиться, но она также генерирует исключение stackoverflow, но я не могу понять, в чем причина.

Может кто-нибудь дать мне подсказку? 

  public void Partition(List<int> valuelist, out List<int> greater, out List<int> lesser)
        {
            lesser = new List<int>();  // <-- Stackoverflow exception here!
            greater = new List<int>();

            if (valuelist.Count <= 1)
                return;

            pivot = valuelist.First();

            foreach (int Element in valuelist)
            {
                if (Element <= pivot)
                    lesser.Add(Element);
                else
                    greater.Add(Element);
            }
        }

        public List<int> DoQuickSort(List<int> list)
        {
            List<int> great;
            List<int> less;

            Partition(list, out great, out less);

            DoQuickSort(great);
            DoQuickSort(less);

            list.Clear();
            list = (List<int>)less.Concat(great);

            return list;

        }

Ответы [ 3 ]

5 голосов
/ 19 января 2010

вы делаете бесконечный цикл прямо там 

  DoQuickSort(great);

вам нужен способ выйти из этого цикла с флагом или условием

Редактировать
Я добавлю, что в режиме отладки с настройками по умолчанию вы можете набрать от 10 000 до 16 000 рекурсивных вызовов до того, как сгенерировано исключение, и от 50 000 до 80 000 в режиме выпуска, все зависит от фактического выполненного кода.

Если вы играете с огромным количеством значений, вам может понадобиться управлять этим рекурсивным вызовом с помощью объекта Stack .

пример кода, чтобы увидеть, сколько звонит до его сбоя;
(отладка; 14 210 вызовов, выпуск 80 071 вызова) 

   static int s = 1;
    static void Main(string[] args)
    {
        o();
    }

    static void o()
    {
        s++;
        Console.WriteLine(s.ToString());
        o();
    }
2 голосов
/ 19 января 2010

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

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

1 голос
/ 19 января 2010

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

Вы должны выбрать значение сводки, удалить элемент сводки из списка (эта часть отсутствует в вашем коде), разделить его на большие и меньшие списки, отсортировать их (рекурсивно),а затем объединить меньший список, элемент pivot (который также, естественно, отсутствует в вашем коде) и больший список.

Я могу опубликовать обновленный, работающий пример кода, но поскольку вы находитесь в "режим обучения ", я буду держать его при себе, пока вы не попросите об этом :)

...