MergeSort Implementation, optimierungsbedraf?

[Jonas Shinaniganz]

Okay also Ich habe die SetLength Befehle gelöscht und setze die länge nur einmal.

Da mein Hilfsarray durch die Länge in der letzten Forschleife auchnoch geregelt hat welche Werte übertragen werden musste Ich das mit dem I erschlagen.


SetLength(ArrayResult, High(IntArray) + 1);

Delphi-Quellcode:

 
for I := I - 1 downto 0 do
begin
  IntArray[StartGO + I] := ArrayResult[I];
end;

Die Abfrage am Anfang habe Ich angepasst und jetzt darf der Startwert nicht mehr größer sein als der Endwert. Finde Ich auch sehr sinnvoll.

if ((Ende - Start > 0) and (Ende > Start)) then (Ende - Start > 0) ist besser als mein (High(IntArray), Hier soll ja nicht nur abgedeckt sein ob der Array der übergeben wurde 1 oder weniger Elemente hat sonder auch die Bereichssortierung berücksichtigt werden, Sodass bei einem Bereich von 1 oder weniger nichts passiert.

Das I := 0; nahe dem Ende ist überflüssig. Stimmt.

Zitat:

Weiterhin würde ich refaktorisieren, d.h. das Mergesort in seine logischen Bestandteile aufteilen:
1. Divide
2. Sort parts
3. Recombine (aka Merge)

Grundsätzlich finde Ich das sehr gut... das Motto Seperation of Concerns bei Klassen und das Divide and Conquer Prinzip sind gut.

Mein Gefühl sagt mir hier keine Trennung vorzunehmen. Manchmal ist es mit kurz und simpel an einem Ort auch getan.

Die Begin und Ends in 1-zeiligen Anweisungen füge Ich immer bei.
Der Lesbarkeit halben. Finde es so übersichtlicher. Sie wegzulassen ist vielleicht auch gut für die Lesbarkeit... hauptsache man macht es einheitlich. Habe es unten bei der Forschleife vergessen und noch hinzugefügt.


Eine Warnung auszugeben, falls der Merge-Sort nicht effizient ist, dazu vielleicht ein Vorschlag für einen anderen Algo wäre cool.

Zitat:

Performancetechnisch könnte man die alte Weisheit aufgreifen, das z.B. ein Straight Insertion Sort für kleine Listen schneller ist. Dann würde man dieses Verfahren anwenden, wenn Ende-Start < 20 ist. Wobei "20" ein eher willkürlicher Wert ist, welchen es zu verifizieren gilt. Es könnte auch andere Verfahren geben (außer SIS), die für kleine N besser sind.

Da müsste man dann noch weiter Überlegen und einen Wert verifizieren. Auch ein guter Vorschlag vielleicht schaffe Ich es ja bis morgen.

Zitat:

Was meinst Du mit 'Optimierungsbedarf'?

genau sowas. Danke

[patti]

Zitat von Jonas Shinaniganz:

Eine Warnung auszugeben, falls der Merge-Sort nicht effizient ist, dazu vielleicht ein Vorschlag für einen anderen Algo wäre cool.

Eine "Warnung" sollte da nicht ausgegeben werden, es soll nur, sobald bei einem Rekursionsschritt festgestellt wird, dass das zu sortierende Intervall kleiner als der festgelegte Wert ist, "automatisch" auf ein anderes Sortierverfahren gewechselt werden, welches bei kleineren Eingabe-Größen effizienter ist (MergeSort bringt nunmal einen gewissen Overhead mit, der sich nur bei größeren Intervallen rentiert).

[Iwo Asnet]

Zitat von Jonas Shinaniganz:

Grundsätzlich finde Ich das sehr gut... das Motto Seperation of Concerns bei Klassen und das Divide and Conquer Prinzip sind gut.

Mein Gefühl sagt mir hier keine Trennung vorzunehmen. Manchmal ist es mit kurz und simpel an einem Ort auch getan.

Das hast Du falsch verstanden. Du kannst deine Implementierung einfach in 5 Einzelroutinen unterteilen, die genau eine Sache machen:
1. Liste in zwei Teile teilen
2. Untere Teilliste sortieren
3. Obere Teilliste sortieren
4. Beide Teillisten in eine neue Liste kopieren (sodaß die neue Liste sortiert ist)
5. Temporäre Liste in die Originalliste zurückkopieren

Der Code steht ja schon da, nur ist er hintereinander in einer Methode. Es wäre von der Ästhetik und Lesbarkeit optimaler, hier zu refaktorisieren.

[Laser]

Moin,

vielleicht wäre eine Parallelisierung interessant? Wenn man z.B. das Sortieren der Teillisten in jeweils einen Thread verlagert?

[Delphi-Laie]

Zitat von Laser:

vielleicht wäre eine Parallelisierung interessant? Wenn man z.B. das Sortieren der Teillisten in jeweils einen Thread verlagert?

Parallelisierung ist bei Mergesort m.E. schwieriger als z.B. bei Quicksort, weil die Threads "synchronisiert" werden müssen, und zwar in der Weise, daß erst, wenn die beiden Teilsortierungen fertig sind - dann aber ohne Verzug - beide Teilmengen verschmolzen werden müssen, während hingegen bei Quicksort die Sortierungen der Teilmengen unabhängig voneinander weiterwerkeln können. Aber mit den richtigen Konzepten (Metaphoren? Keine Ahnung) ist eine solche Synchronisierung sicher möglich.

Am Mergesort selbst läßt sich zum einen die Rekursion beseitigen, aber der Algorithmus als solcher bleibt dabei bestehen, nur der Stackbedarf wird vermieden.

Die eigentliche Optmierung des Mergesorts besteht allerdings darin, von einem Tiefen- zu einem Breitenalgorithmus überzugehen, konkret zum sog. Natura Mergesort, das bei entsprechender Implementation in der Lage ist, Vorsortierungen auszunutzen und ggf. auch invertierte Teilfolgen "richtigherum zu invertieren".