eccezione QuickSort e stack overflow

Question

Credo che QuickSort in alcune condizioni specifiche può causare un'eccezione di overflow dello stack.

Ci sono due modi di selezionare l'elemento di perno durante il processo di ordinamento - il valore pivot può essere l'elemento al centro del range ordinato o l'elemento scelto casualmente (nell'intervallo ordinata). È il secondo metodo (casuale) meno overflow dello stack inclini rispetto al primo? La prego di consigliarmi?

Ecco la mia versione di rapido sort (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;

Grazie per i vostri consigli in anticipo!

Mariusz.

Answer 1

Utilizzando qualsiasi elemento in un indice specifico (primo, ultimo o medio) come elemento di rotazione incorre sempre il rischio di degenerazione con set di dati specifici. elemento primo e l'ultimo sono particolarmente cattivi perché degenerano con dati preordinati (o quasi) precedentemente ordinati, che è abbastanza comune. L'elemento centrale è meno problematico in pratica, ma ancora vulnerabile a insiemi di dati costruito in modo pericoloso.

Utilizzo di un elemento casuale significa degenerazione può avvenire solo attraverso pura sfortuna (assumendo che il RNG non è prevedibile per un ipotetico attaccante), quindi è una buona tattica. Un ulteriore miglioramento che riduce significativamente la probabilità di essere colpiti da tale sfortuna sarebbe quella di utilizzare la mediana di 3 (o 5, o più) elementi scelti a caso, ma deve essere calibrato contro la complessità supplementare e durata questo comporta.

Answer 2

Un modo probabilistico per migliorare l'efficienza è quello di scegliere 3 elementi casuali e utilizzare il valore medio (quello che non è il massimo, né il minimo).

È inoltre possibile utilizzare una pila di record da inserire ed estrarre i limiti e scrivere un ciclo invece di fare chiamate ricorsive (anche userà meno memoria in quanto il puntatore alla matrice non avrà bisogno di essere replicato per tutte le chiamate ).

EDIT: Ho notato che la procedura interna non prende il puntatore come parametro, in modo da dimenticare che una parte ^ _ ^ comunque, lo stack frame ha più informazioni che solo i parametri della funzione, quindi sarà ancora più efficiente della memoria (e il punto principale era che il cumulo erano stack dei dati viene allocata è solitamente maggiore della pila processo).

Answer 3

Grazie per le vostre risposte.

Fortran, grazie per i vostri suggerimenti in materia di fare un metodo non ricorsivo. Basandosi su di loro, sono riuscito a fare una quick sort iterational e sembra funzionare correttamente:.)

Ecco il codice:

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;

Spero ho implementato in modo ottimale. Ho usato un array dinamico per memorizzare i confini di ordinamento (ciascuna coppia di elementi è bassa e alta bound).

Questo metodo iterational sembra essere leggermente più lento rispetto a quello ricorsiva, ma penso che non importa tanto.

Se si nota un errore o si conosce un modo per ottimizzare il metodo, sarò grato se me lo faccia sapere.

Grazie!

Mariusz.

Answer 4

Un'implementazione quicksort decente utilizza O (log n) spazio di stack. Raggiunge che di classificare il più piccolo sottoarray prima. Nel peggiore dei casi, se non si fa che è la situazione in cui il perno è l'elemento più grande e si tenta l'ordinamento di un sottoarray che è solo un piccolo ogni volta. Questo si verifica quando si utilizza i dati già ordinati come input e prendere come perno l'elemento giusto.

L'implementazione esplicita stack è più lenta e soffre lo stesso problema (anche se ora è mucchio invece di pila).

Un'altra cosa che manca è un interruttore di inserzione quando la sottomatrice è piccolo (5-25 elementi). Anche dare un'occhiata alle domande Quicksort dual-perno su questo sito.