Otro Quicksort stackoverflow

Question

Así que he estado tratando de implementar un quicksort mí, sólo para aprender algo de él, pero también genera un stackoverflowexception, pero me parece que no puede encontrar la causa.

Alguien puede darme una pista?

  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

Usted no está poniendo ninguna condición en sus llamadas recursivas a DoQuicksort, por lo que nunca va a dejar de recursividad, dando lugar a un desbordamiento de pila. Sólo debe estar llamando DoQuicksort en una lista si contiene más de un elemento.

Editar Como Will dijo en su comentario, este es un enfoque muy lento a "ordenación rápida". Usted debe buscar en los algoritmos de partición en el lugar, como se mencionó en la Wikipedia artículo ordenación rápida .

Answer 2

que está haciendo un bucle infinito allí mismo

  DoQuickSort(great);

necesita una manera de salir de ese bucle con una bandera o una condición

Editar
Voy a añadir que en el modo de depuración, con la configuración por defecto, sólo se puede alcanzar entre 10.000 y 16.000 antes llamada recursiva se produce una excepción y entre 50.000 y 80.000 cuando se encuentra en modo de lanzamiento, todo dependerá del código real ejecutado.

Si juegas con un gran número de valores, puede que tenga que dirigirse a sí mismo que la llamada recursiva mediante el uso de un objeto Stack .

código de ejemplo para ver la cantidad de llamadas antes de que se desplome;
(Depuración; 14.210 llamadas, llamada liberar 80.071)

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

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

Answer 3

Creo que uno de los problemas en el código que mantenga el valor dinámico cuando se crean particiones en la lista.Esto significa que usted se encontrará en una situación en la que todos los valores de la partición en mayor o menos, y la partición va a dejar de trabajar.De esta forma, no le permite dividir una de las listas anylonger, por lo que la condición de salida de la Partición método nunca está satisfecho.

Usted debe seleccionar un valor dinámico, quitar el elemento pivote de la lista (esta parte es la que falta en el código), partición es mayor y menos listas, ordenar los (de forma recursiva), y luego concatenar la menos lista, el elemento pivote (esto es también, naturalmente, que falta en el código) y el mayor de la lista.

Me pueden enviar una versión actualizada, de trabajo, código de ejemplo, pero ya que está en "modo de aprendizaje", voy a mantener a mí mismo hasta que la pida :)