Iteratives Mergesort mit Stackemulation

[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.