Excepción de QuickSort y desbordamiento de pila

Question

Creo que QuickSort en algunas condiciones específicas puede provocar una excepción de desbordamiento de pila.

Hay dos formas básicas de seleccionar el elemento pivote durante el proceso de clasificación: el valor pivote puede ser el elemento en el medio del rango ordenado o el elemento elegido al azar (dentro del rango ordenado).¿El segundo método (aleatorio) es menos propenso a desbordarse que el primero?¿Podrías aconsejarme?

Aquí está mi versión de clasificación rápida (Delphi):

procedure QuickSort(lLowBound, lHighBound: integer; lCompare: TListSortCompare;
  lSwap: TListSortSwap);

  procedure Sort(lLowIndex, lHighIndex: integer);
  var
    lLeft: Integer;
    lRight: Integer;
    lPivot: Integer;
    lLeftCompare: Integer;
    lRightCompare: Integer;
  begin
    repeat
      lLeft := lLowIndex;
      lRight := lHighIndex;
      lPivot := (lLowIndex + lHighIndex) div 2; //the pivot as the element in the middle
      //lPivot := lLowIndex + Random(lHighIndex - lLowIndex + 1); //the pivot chosen randomly
      repeat
        lLeftCompare := lCompare(lLeft, lPivot);
        while lLeftCompare < 0 do
        begin
          Inc(lLeft);
          lLeftCompare := lCompare(lLeft, lPivot);
        end;
        lRightCompare := lCompare(lRight, lPivot);
        while lRightCompare > 0 do
        begin
          Dec(lRight);
          lRightCompare := lCompare(lRight, lPivot);
        end;

        if lLeft <= lRight then
        begin
          if not ((lLeftCompare = 0) and (lRightCompare = 0)) then
          begin
            lSwap(lRight, lLeft);

            if lPivot = lLeft then
              lPivot := lRight
            else if lPivot = lRight then
              lPivot := lLeft;
          end;
          Inc(lLeft);
          Dec(lRight);
        end;
      until lLeft > lRight;

      if (lLowIndex < lRight) then
        Sort(lLowIndex, lRight);

      lLowIndex := lLeft;
    until lLeft >= lHighIndex;
  end;

begin
  if lHighBound > lLowBound then
    Sort(lLowBound, lHighBound);
end;

¡Gracias por tu consejo de antemano!

Mariusz.

Answer 1

El uso de cualquier elemento en un índice específico (primero, último o medio) como el elemento de pivote siempre incurre en el riesgo de degeneración con conjuntos de datos específicos. Primer y último elemento es particularmente malo porque degeneran con los datos ordenados previamente (o casi) preclasificados, que es bastante común. El elemento medio es menos problemático en la práctica, pero todavía vulnerables a los conjuntos de datos construido maliciosamente.

Uso de un elemento aleatorio significa degeneración sólo puede ocurrir a través de la mala suerte puro (suponiendo que el RNG no es predecible por un atacante hipotético), por lo que es una buena táctica. Otra mejora que reduce significativamente la probabilidad de ser golpeado por que la mala suerte sería el uso de la mediana de 3 (o 5, o más) elementos escogidos al azar, pero tiene que ser ponderado frente a la complejidad adicional y el tiempo de ejecución de este incurre.

Answer 2

Una manera probabilística para mejorar la eficiencia es escoger 3 elementos aleatorios y utilizar el valor medio (el que no es el más grande ni el menos).

También puede utilizar una pila de discos para empujar y hacer estallar los límites y escribir un bucle en lugar de hacer llamadas recursivas (también usará menos memoria ya que no tendrá que ser replicado por todas las llamadas el puntero a la matriz ).

EDIT: Me he dado cuenta de que el procedimiento interno no toma el puntero como parámetro, por lo que se olvide esa parte ^ _ ^ de todos modos, que la pila tiene más información que sólo los parámetros de la función, por lo que será aún más eficiente de la memoria (y el punto principal es que el montón eran la pila de datos se asigna es generalmente más grandes que la pila de proceso).

Answer 3

Gracias por tus respuestas.

Fortran, gracias por sus sugerencias sobre cómo crear un método no recursivo.Basándome en ellos, logré hacer una clasificación rápida iterativa y parece estar funcionando correctamente :).

Aquí está el código:

procedure QuickSortI(lLowBound, lHighBound: integer; lCompare: TListSortCompare;
  lSwap: TListSortSwap);
var
  lLeft: Integer;
  lRight: Integer;
  lPivot: Integer;
  lLeftCompare: Integer;
  lRightCompare: Integer;
  lStack: array of integer;
  lStackLen: integer;
begin
  if lHighBound > lLowBound then
  begin
    lStackLen := 2;
    SetLength(lStack, lStackLen);
    lStack[lStackLen - 1] := lLowBound;
    lStack[lStackLen - 2] := lHighBound;

    repeat
      lLowBound := lStack[lStackLen - 1];
      lHighBound := lStack[lStackLen - 2];
      SetLength(lStack, lStackLen - 2);
      Dec(lStackLen, 2);

      lLeft := lLowBound;
      lRight := lHighBound;
      lPivot := (lLowBound + lHighBound) div 2;
      repeat
        lLeftCompare := lCompare(lLeft, lPivot);
        while lLeftCompare < 0 do
        begin
          Inc(lLeft);
          lLeftCompare := lCompare(lLeft, lPivot);
        end;
        lRightCompare := lCompare(lRight, lPivot);
        while lRightCompare > 0 do
        begin
          Dec(lRight);
          lRightCompare := lCompare(lRight, lPivot);
        end;

        if lLeft <= lRight then
        begin
          if not ((lLeftCompare = 0) and (lRightCompare = 0)) then
          begin
            lSwap(lRight, lLeft);

            if lPivot = lLeft then
              lPivot := lRight
            else if lPivot = lRight then
              lPivot := lLeft;
          end;
          Inc(lLeft);
          Dec(lRight);
        end;
      until lLeft > lRight;

      if (lHighBound > lLeft) then
      begin
        Inc(lStackLen, 2);
        SetLength(lStack, lStackLen);
        lStack[lStackLen - 1] := lLeft;
        lStack[lStackLen - 2] := lHighBound;
      end;

      if (lLowBound < lRight) then
      begin
        Inc(lStackLen, 2);
        SetLength(lStack, lStackLen);
        lStack[lStackLen - 1] := lLowBound;
        lStack[lStackLen - 2] := lRight;
      end;

    until lStackLen = 0;
  end;
end;

Espero haberlo implementado de manera óptima.Utilicé una matriz dinámica para almacenar los límites de clasificación (cada par de elementos es el límite inferior y superior).

Este método iterativo parece ser un poco más lento que el recursivo, pero creo que no importa tanto.

Si notas algún error o conoces alguna manera de optimizar el método, te agradeceré que me lo hagas saber.

¡Gracias!

Mariusz.

Answer 4

Una implementación quicksort decente utiliza O (log n) espacio de pila. Logra que por la clasificación de la primera subserie más pequeño. Peor de los casos si no lo hace es la situación en la que el pivote es el elemento más grande y se intenta clasificar un subconjunto que es sólo un pequeño cada vez. Esto se produce al utilizar los datos ya almacenados como entrada y toma como pivote el elemento de la derecha.

Su aplicación explícita pila es más lento y sufre del mismo problema (aunque ahora es del montón en lugar de pila).

Otra cosa que falta es un cambio a la ordenación por inserción cuando el subconjunto es pequeño (5-25 elementos). También echa un vistazo a las preguntas quicksort de doble pivote en este sitio.