Iteratives Mergesort mit Stackemulation

[Delphi-Laie]

Beim einfachen Mergesort störte mich dessen von der Rekursion verursachte Stackbeanspruchung, und ich versuchte mithin, diese Rekursion bzw. Stackbeanspruchung zu eliminieren bzw. zu emulieren (oder zu ersetzen), und zwar mit einem schnöden Array. Mit der in R. Sedgewicks Standardwälzer vorgeschlagenen Methode, beispielhaft am Quicksort, kam ich einfach nicht weiter. Vielleicht liegt es daran, daß beim Quicksort bei der Abwärtsbewegung der Rekursion sortiert wird (top-down?), beim Mergesort hingegen erst bei der Aufwärtsbewegung derselben (bottom-up?). Wie es genau bezeichnet wird, ist mir nicht bekannt. Jedenfalls tat ich mich daran, auch für diesen Sortieralgorithmus eine stackbefreite Variante zu generieren, was mir auch nach knapp 2 Tagen endlich gelang. Dabei ist der zweite Aufruf der beiden Rekursivaufrufe

Delphi-Quellcode:

if mitte>links then mergesort(links,mitte);
if rechts>succ(mitte) then mergesort(succ(mitte),rechts);

nicht mehr offensichtlich erkennbar.

Wohlgemerkt: Es geht hier nicht um das von Natur aus iterative sog. Natural Mergesort, bei dem anfängliche vorhandene sortiert vorliegende Teilmengen/-folgen gesucht und gefunden werden und der Algorithmus schrittweise „nach oben“ auf diesen aufbaut. Ebensowenig bedarf die iterative Stackemulation, daß die Anzahl der zu sortierenden Elemente eine Zweierpotenz sein muß (derartige Mergesortvarianten gibt es auch), denn das ist beim gewöhnlichen rekursiven Mergesort ja auch nicht der Fall.

Ich fand dazu im Internet jedenfalls nichts.

Kurzum, hier das nunmehr anscheinend fehlerfreie Resultat:

Delphi-Quellcode:

procedure mergesort(links,rechts:word);
var
stack:array {[0..x]} of byte;{oder word oder integer oder cardinal o.ä,
statisch oder dynamisch zu deklarieren und natürlich auch ausreichend zu dimensionieren...}
mitte,richtung,stackzaehler:word;//Richtung: 0 bedeutet ab-, 1 bedeutet aufwärts
begin
  richtung:=0; //Richtung 0 bedeutet Ab-, Richtung 1 Aufwärtsbewegung
  stackzaehler:=2;
  stack[1]:=0; //nötig wegen der Befehlszeile unten: rechts:=stack[pred(stackzaehler)]
  repeat
  mitte:=(links+rechts) div 2;
  if (richtung=0) and (mitte>links) then //neue Intervallgrenzen ermitteln
    begin
    //mergesort(links,mitte);
    stack[stackzaehler]:=links;
    stack[succ(stackzaehler)]:=rechts;
    inc(stackzaehler,2);
    rechts:=mitte
    end;

  if ((richtung=0) and ((mitte=links)) and (succ(mitte)<=rechts))  //Sortierung 2er einzelner Elemente
  or (richtung=1) //Sortierung durch Mischen sortierter Teilmengen
  then
     begin
     {Hier erfolgt das Verschmelzen („Mergen“) der beiden schon sortierten Teilmengen
      links - mitte und succ(mitte) - rechts
      mit einem Algorithmus beliebiger Wahl (z.B. in meinem Sortierkino}
     end;

    if (links=mitte) or (richtung=1) then
      begin
      if rechts<stack[pred(stackzaehler)] then
        begin //nach „rechts“ hinübergehen
        richtung:=0;
        links:=succ(rechts);
        rechts:=stack[pred(stackzaehler)]
        end
      else
        begin //wieder „auftauchen“
        richtung:=1;
        dec(stackzaehler,2);
        links:=stack[stackzaehler];
        rechts:=stack[succ(stackzaehler)]
        end
      end
  until stackzaehler=0
end;

Edit [17.04.2011, 15:20]: Code geändert

[FredlFesl]

Wo ist der Vorteil ggü. der rekursiven Version, außer das es schlechter lesbar ist?

[Namenloser]

Zitat von FredlFesl:

Wo ist der Vorteil ggü. der rekursiven Version, außer das es schlechter lesbar ist?

Kein Stackoverflow bei großen Datenmengen.

[Satty67]

Wie stark wird den der Stack belastet? Ich bin mir MergeSort nicht richtig vertraut.

(Ist das zu OT oder hier erlaubt: Bei welcher Anforderung ist MergeSort noch ideal? Meine das MergeSort sich in jedem Gebiet einem besser geeigneten Algorithmus geschlagen geben muss, weshalb ich mich bisher auch kaum damit beschäftigt hatte. Ist keine eigene Erfahrung, nur "angelesen").

[JasonDX]

Zitat von NamenLozer:

Zitat von FredlFesl:

Wo ist der Vorteil ggü. der rekursiven Version, außer das es schlechter lesbar ist?

Kein Stackoverflow bei großen Datenmengen.

Bei welchen Großen Datenmengen erwartest du denn einen Stackoverflow? Ich schätze mal, 512 rekursive Aufrufe sollten noch gehn. Die Tiefe bei Mergesort für eine Menge der Mächtigkeit n liegt bei ld(n), folglich, um nicht 512 rekursive Aufrufe zu überschreiten, darf die zu Sortierende Menge nicht mehr als 2^512 Elemente enthalten. Wenn sich mein Kopf nicht verrechnet hat, sind das ca. 10^150 Elemente, ab denen die Rekursionstiefe von 512 erreicht werden würde.

greetz
Mike

[Delphi-Laie]

Eine Grundsatzdiskussion wollte und erwartete ich eigentlich nicht.

Es gibt Leute, die die Rekursion nicht mögen, auch wenn die kürzeren Quelltexte natürlich übersichtlicher (und nicht etwa schlecher lesbar, das ist etwas anderes) und damit weniger fehleranfällig sind.

Hinzu kommt, daß man jegliches Risiko des Stacküberlaufes ausschließt - auch wenn man den Stack maximiert, kann man sich bei ihm eigentlich nie sicher sein, daß er - insbesondere, weil auch andere Routinen darauf zugreifen könnten - doch überläuft. Dimensioniert man den Hilfs-/Pseudostack (Array) hingegen dynamisch während der Laufzeit des Sortierens bei Bedarfe neu, so sind Speicherüberläufe praktisch ausgeschlossen.

Letztlich ging es hier (und mir) nur darum, zu zeigen, wie man die Rekursion auch des klassischen Mergesorts beseitigt bekommt (bzw. bekommen kann).

Zitat von Satty67:

Wie stark wird den der Stack belastet? Ich bin mir MergeSort nicht richtig vertraut.

(Ist das zu OT oder hier erlaubt: Bei welcher Anforderung ist MergeSort noch ideal? Meine das MergeSort sich in jedem Gebiet einem besser geeigneten Algorithmus geschlagen geben muss, weshalb ich mich bisher auch kaum damit beschäftigt hatte. Ist keine eigene Erfahrung, nur "angelesen").

Nein, Mergesort muß sich ganz und gar nicht geschlagen geben. Mergesort hat in jedem Falle nur eine n*log(n)-Komplexität/Laufzeit (im Gegensatz zu Quicksort) und kann zudem stabil implementiert werden (im Gegensatz zu Quick- und Heapsort). Der einzige verbliebene Nachteil, daß es zusätzlichen Speicher zum Verschmelzen der schon sortierten Teilmengen benötigt, stimmt auch nicht mehr, denn auch dafür gibt es Lösungen (die ich in meinem Sortierprogramm einfügte).

[FredlFesl]

Mergesort zeichnet sich durch die sehr geringe Anzahl an Datenbewegungen aus. Mit diesem Sortierverfahren lassen sich Dateien sehr effizient sortieren (record by record).

[Delphi-Laie]

Der Vollständigkeit halber möchte ich noch eine Alternativversion des rekursionsfreien Mergesorts anbieten, die zum einen für ziemlich viele "Entrekursivierungen" geeignet zu sein scheint (bei Endrekursionen geht es allerdings auch einfacher, und bei verschachtelten dürfte es scheitern) und zum anderen sich eines etwas ausgereifteren Stackemulators bedient (auf der Grundlage von Roberts Sedgewicks Buch "Algorithmen"):

Delphi-Quellcode:

type link=^node;
 node=record
   key:word;
   next:link
   end;

  TStackemulator=class
  head,z:link;
  constructor create(a:word);
  destructor destroy;override;
  procedure push(v:word);
  function pop:word;
  function isempty(autodelete:boolean):boolean;
  procedure pop3(var a,b,c:word);
  procedure push3(a,b,c:word);
  end;

constructor TStackemulator.create(a:word);
var l:word;
begin
new(head);
new(z);
head^.next:=z;
z^.next:=z;
for l:=1 to a do push(0)
end;

destructor TStackemulator.destroy;
begin
//inherited//funktioniert auch hier und sogar mit beiden inherited
z^.next:=nil;
head^.next:=nil;
z:=nil;
head:=nil;
dispose(z);
dispose(head);
inherited
end;

procedure TStackemulator.push(v:word);
var t:link;
begin
new(t);
t^.key:=v;
t^.next:=head^.next;
head^.next:=t
end;

function TStackemulator.pop:word;
var t:link;
begin
t:=head^.next;
result:=t^.key;
head^.next:=t^.next;
dispose(t)
end;

function TStackemulator.isempty(autodelete:boolean):boolean;
begin
result:=head^.next=z;
if result and autodelete then destroy
end;

procedure TStackemulator.push3(a,b,c:word);
begin
push(a);
push(b);
push(c)
end;

procedure TStackemulator.pop3(var a,b,c:word);
begin
c:=pop;
b:=pop;
a:=pop
end;

procedure mergesort(links,rechts:word);
label 1,2;
var mitte,Position:word;
Stackemulator:TStackemulator;
begin
Stackemulator:=TStackemulator.create(3);//mit 3 Leerelementen ("0") füllen, da (bei diesem Algorithmus) immer 3 Elemente abgelegt und abgerufen werden
  repeat
  mitte:=(links+rechts) div 2;
  if links<mitte then
    begin
    Stackemulator.push3(links,rechts,1);
    rechts:=mitte;
    continue
    end;
  1:if succ(mitte)<rechts then
    begin
    Stackemulator.push3(links,rechts,2);
    links:=succ(mitte);
    continue
    end;
  2:merge(links,mitte,rechts);//hier einen beliebigen Mergealgorithmus einfügen bzw. ausführen, 1. Teilarray: von links bis mitte, 2. Teilarrary: von mitte+1 bis rechts
  Stackemulator.pop3(links,rechts,Position);
  mitte:=(links+rechts) div 2;
  case Position of
    1:goto 1;
    2:goto 2
    end
  until Stackemulator.isempty(true)//bei Leersein automatisch löschen
end;

[Benmik]

Die verlinkte Webseite ("Sortierkino") ist schon beeindruckend. Man hat schon geahnt, dass es noch so einiges jenseits von Quick- und Bubblesort gibt, aber das ist wirklich eine erschlagende Fülle. Ich hielt Quicksort für den Allgemeingebrauch immer für den Algorithmus der Wahl (und fühlte mich dadurch bestätigt, dass Delphi ihn ja auch für Binary Search nimmt), aber das muss man vielleicht überdenken.

[Delphi-Laie]

Danke für die Anerkennung!

Zitat von Benmik:

Die verlinkte Webseite ("Sortierkino") ist schon beeindruckend. Man hat schon geahnt, dass es noch so einiges jenseits von Quick- und Bubblesort gibt, aber das ist wirklich eine erschlagende Fülle.

Nunja, viele der in meinem Programm angebotenen Algorithmen sind nur eine Modifikation bekannter Algorithmen, die ich aber aus Demonstrationsgründen wert erachtete, als separaten Eintrag mit aufzunehmen / -führen.

Zitat von Benmik:

Ich hielt Quicksort für den Allgemeingebrauch immer für den Algorithmus der Wahl (und fühlte mich dadurch bestätigt, dass Delphi ihn ja auch für Binary Search nimmt), aber das muss man vielleicht überdenken.

Für die Erstsortierung - dann logischerweise unsortierter - Daten trifft das auch zu, dafür ist Quicksort wirklich die Wahl ohne Qual, weil es der schnellste der In-Situ-Algorithmen ist. Bei bereits sortierten Daten macht sich jedoch die Nichstabilität des Quicksorts unangenehm bemerkbar. Außerdem droht der Algorithmus dann bei bestimmten Strukuturen der Eingangsmenge zu entarten (quadratische Komplexität). Es gibt natürlich auch Lösungen, die die Wahrscheinlichkeit dafür auf ein Minimum reduzieren (oder ganz beseitgen?), so z.B. das 3-Wege-Quicksort. Weiterer Aspekt: Quicksort ist mit akzeptablem Aufwand auch für mittelmäßig routinierte Programmierer zu implementieren.