QuickSort und Stapelüberlaufausnahme

Question

Ich denke, dass QuickSort in einigen bestimmten Bedingungen einen Stapelüberlauf Ausnahme verursachen kann.

Es gibt zwei grundlegende Möglichkeiten des Auswählens des Drehelements während des Sortierprozesses - das Schwenkwert das Element in der Mitte der sortierten Bereich oder dem Element zufällig (innerhalb der sortierten Bereich) gewählt werden kann. Ist das zweite Verfahren (random) Stapelüberlauf weniger anfällig ist als der erste? Könnten Sie mir bitte raten?

Hier ist meine Version von Quicksort (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;

Vielen Dank für Ihre Beratung im Voraus!

Mariusz.

Answer 1

jedes Element an einem bestimmten Index verwenden (erster, letzte oder Mitte) als Schwenkelement entsteht immer das Risiko einer Entartung mit spezifischen Datensatz. Erstes und letztes Element ist besonders schlecht, weil sie mit vorsortiert (oder fast vorsortierten) Daten degenerieren, was durchaus üblich ist. Das mittlere Element ist weniger problematisch in der Praxis aber immer noch anfällig Datensätze in böswilliger Absicht gebaut.

ein zufälliges Elements Mit der Benutzung Degeneration nur durch reines Pech passieren kann (unter der Annahme, dass die RNG von einem hypothetischen Angreifer nicht vorhersehbar ist), so ist es eine gute Taktik. Eine weitere Verbesserung, die signifikant die Wahrscheinlichkeit verringert, durch dieses Pech getroffen zu werden, wäre es, den Median von 3 zu verwenden (oder 5 oder mehr) zufällig ausgewählten Elementen, aber es hat gegen die zusätzliche Komplexität zu gewichten und die Laufzeit dieses entsteht.

Answer 2

Eine probabilistische Art und Weise zur Verbesserung der Effizienz ist 3 zufällige Elemente auswählen und den mittleren Wert verwenden (die, die nicht die größte, noch die am wenigsten ist).

Sie können auch einen Stapel von Datensätzen verwenden zu schieben und die Grenzen Pop und eine Schleife, anstatt, rekursive Aufrufe schreiben (auch wird es weniger Speicher, da der Zeiger auf das Array wird nicht für alle Anrufe repliziert werden müssen, ).

EDIT: Ich habe bemerkt, dass das interne Verfahren die Zeiger als Parameter nicht angenommen hat, so vergessen, dass ein Teil ^ _ ^ wie auch immer, der Stapelrahmen mehr Informationen hat als nur die Parameter der Funktion, so wird es nach wie vor mehr Speicher effizienter (und die Hauptsache war, dass der Haufen der Datenstapel waren zugeordnet ist, in der Regel größer als der Prozess-Stack).

Answer 3

Vielen Dank für Ihre Antworten.

Fortran, vielen Dank für Ihre Anregungen zu einer nicht-rekursive Methode zu machen. Basierend auf ihnen gelang es mir, ein Iterationsverfahren schnelle Art zu machen, und es scheint, richtig zu funktionieren.)

Hier ist der Code:

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;

Ich hoffe, dass ich es in optimaler Weise umgesetzt. I verwendet ein dynamisches Array die Sortiergrenzen zu speichern (wobei jedes Paar von Elementen ist, die niedrige und hohe bound).

Diese Iterationsverfahren Methode scheint etwas langsamer als die rekursive zu sein, aber ich denke, es ist nicht so wichtig.

Wenn Sie einen Fehler bemerken oder Sie kennen eine Möglichkeit, das Verfahren zur Optimierung, werde ich Ihnen dankbar, wenn Sie lassen Sie mich wissen.

Danke!

Mariusz.

Answer 4

Eine anständige quicksort Implementierung verwendet O (log n) Stapelspeicher. Es wird erreicht, dass, indem zuerst das kleinste Sub-Array zu sortieren. Im schlimmsten Fall, wenn Sie das nicht tun, ist die Situation, in der die Dreh das größte Element ist und Sie versuchen, Sortieren einen Sub-Array, das nur ein kleinen jedes Mal ist. Dies geschieht, wenn Sie bereits sortierten Daten als Eingabe verwenden und als Drehpunkt das richtige Element nehmen.

Ihre explizite Stack-Implementierung ist langsamer und leidet unter dem gleichen Problem (obwohl es jetzt ist Haufen statt Stack).

Eine andere Sache fehlt, ist ein Wechsel zu Insertionsort, wenn das Sub-Array klein (5-25 Elemente). Werfen Sie auch einen Blick auf den Dual-Pivot-quicksort Fragen auf dieser Seite.