Еще один Quicksort stackoverflow

Question

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

Может ли кто-нибудь дать мне ключ?

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; 

     } 

Answer 1

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

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

Answer 2

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

DoQuickSort(great); 

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

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

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

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

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

    static void o() 
    { 
     s++; 
     Console.WriteLine(s.ToString()); 
     o(); 
    } 

Answer 3

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

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

я могу опубликовать обновленный, рабочий, образец кода, но так как вы находитесь в «режиме обучения», я буду держать это в себе, пока вы не попросите его :)