QuickSort e estouro de pilha de exceção

Question

Eu acho que QuickSort em algumas condições específicas podem causar uma exceção de estouro de pilha.

Existem duas formas básicas de selecionar o elemento pivot durante o processo tipo - o valor do pivô pode ser o elemento no meio do intervalo classificado ou o elemento escolhido aleatoriamente (dentro do intervalo classificado). É o segundo método (aleatório) estouro menos pilha propensas do que o primeiro? Você poderia me aconselhar?

Aqui é a minha versão de classificação 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;

Obrigado por seu conselho de antecedência!

Mariusz.

Answer 1

O uso de qualquer elemento em um índice específico (primeira, a última ou meio) como o elemento de articulação sempre incorre no risco de degeneração com conjuntos de dados específicos. Primeiro e último elemento são particularmente ruim porque eles degeneram com pré-classificados (ou quase pré-classificados) de dados, que é bastante comum. O elemento do meio é menos problemática na prática, mas ainda vulnerável a conjuntos de dados de forma maliciosa construídos.

Usando um aleatória degeneração meios elemento só pode acontecer através de pura má sorte (assumindo que o RNG não é previsível por um atacante hipotético), por isso é uma boa tática. Uma outra melhoria que reduz significativamente a probabilidade de ser atingido por essa má sorte seria usar a mediana de 3 (ou 5 ou mais) elementos escolhidos aleatoriamente, mas tem que ser ponderado contra a complexidade adicional e tempo de execução isso incorre.

Answer 2

Uma maneira probabilística para melhorar a eficiência é escolher 3 elementos aleatórios e usar o valor médio (o que não é o maior nem o mínimo).

Você também pode usar uma pilha de registros para empurrar e pop dos limites e escrever um loop em vez de fazer chamadas recursivas (também ele usará menos memória desde o ponteiro para a matriz não precisará ser replicado para todas as chamadas ).

EDIT: Eu tenho notado que o procedimento interno não leva o ponteiro como parâmetro, para esquecer essa parte ^ _ ^ de qualquer maneira, o quadro de pilha tem mais informação do que apenas os parâmetros da função, por isso vai ser ainda memória mais eficiente (e o ponto principal era que a pilha foram a pilha de dados é alocado é geralmente maior do que a pilha de processo).

Answer 3

Obrigado por suas respostas.

Fortran, obrigado por suas sugestões sobre tornando um método não-recursivo. Baseando-los, consegui fazer uma classificação rápida iterational e parece estar funcionando corretamente:.)

Aqui está o 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 implementou em uma ótima forma. Eu usei uma matriz dinâmica para armazenar os limites de classificação (cada par de itens é a baixa e alta bound).

Este método iterational parece ser um pouco mais lento do que o recursiva, mas acho que isso não importa tanto.

Se você notar um erro ou você sabe uma maneira de otimizar o método, eu serei grato se você me avise.

Obrigado!

Mariusz.

Answer 4

Um espaço de pilha decente usos implementação quicksort O (log n). Ele consegue que classificando o menor subarray primeiro. Na pior das hipóteses, se você não fazer isso é a situação em que o pivô é o maior elemento e você tentar classificar um subarray que é apenas um menor de cada vez. Isso ocorre quando você usar dados já classificados como entrada e tomar como pivô o elemento certo.

A implementação pilha explícita é mais lento e sofre do mesmo problema (embora agora é pilha em vez da pilha).

Outra coisa que falta é um interruptor de tipo de inserção quando o subarray é pequena (5-25 elementos). Também dê uma olhada nas perguntas quicksort dual-pivô neste site.