Un altro Quicksort stackoverflow

Question

Così sto cercando di implementare un quicksort me, solo per imparare qualcosa da esso, ma genera anche un stackoverflowexception, ma non riesco a trovare quale sia la causa.

Qualcuno può darmi un indizio?

  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

Non stai mettendo tutte le condizioni relative alle proprie chiamate ricorsive per DoQuicksort, in modo che non smetterò mai di recursing, portando ad un overflow dello stack. Si dovrebbe essere chiamando solo DoQuicksort in un elenco se contiene più di un elemento.

Modifica Come Will ha detto nel suo commento, questo è un approccio molto lento a "Quicksort". Si dovrebbe guardare gli algoritmi di partizionamento sul posto, come indicato sul articolo Quicksort .

Answer 2

si sta facendo un ciclo infinito proprio lì

  DoQuickSort(great);

è necessario un modo per uscire da quel ciclo con una bandiera o di una condizione

Modifica
Vorrei aggiungere che in modalità debug, con impostazione di default, si può raggiungere solo tra 10.000 e 16.000, prima chiamata ricorsiva viene generata un'eccezione e tra 50.000 e 80.000 quando è in modalità di rilascio, tutto dipenderà dal codice vero e proprio eseguito.

Se si gioca con un enorme numero di valori, potrebbe essere necessario per gestire te stesso che chiamata ricorsiva utilizzando un Stack oggetto.

codice di esempio per vedere quanto di chiamata prima di schianto;
(Debug; 14.210 chiamata, rilasciare 80.071 chiamata)

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

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

Answer 3

Penso che uno dei problemi nel codice che è possibile mantenere il valore pivot per il partizionamento di elenco.Questo significa che si esegue in una situazione in cui tutti i valori partizione in più o in meno, e il partizionamento smetterà di funzionare.Questo ti permetterà di non lasciare che la divisione di una delle liste anylonger, in modo che la condizione di uscita nella Partizione metodo non è mai soddisfatta.

È necessario selezionare un valore pivot, rimuovere il perno elemento dall'elenco (questa parte è assente nel codice), parition in maggiore e minore liste, specie quelli (ricorsivamente), e poi concatenare meno di un elenco, il pivot elemento (anche questo è, naturalmente, manca nel tuo codice) e l'elenco più ampio.

Posso pubblicare un aggiornamento, di lavoro, codice di esempio, ma visto che sono in "modalità di apprendimento", voglio tenere per me fino a quando chiedete :)