Mergesort ohne extra Speicher

Heiko · Beiträge: 3169 Erhaltene Danke: 11

Hi @all,

wir sollen momentan eine MergeSort von der Schule aus programmieren, aber mit einer kleinen Optimierung, wozu ich bei Google etc. bisher nichts gefunden habe

. Und zwar sollen wir kein Hilfsarray beim "mergen" (mischen) verwenden. Nur irgendwie haut das bei mir nicht hin (kommt immer irgendein Schrott raus, wo Zahlen überschreiben werden :arrow:

einige Zahlen sind dementsprechend zu oft da

). Seht ihr mein Denkfehler bzw. einen allgemeienen Fehler?

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:

var
  SortArray: array of integer;

procedure MergeSort(Left, Right: Integer);
var
  Middle: Integer;

  procedure Merge;
  var
    x, y: Integer;
    IntBackUp: Integer;
    Mid: Integer;
  begin
    x:=Left;
    Mid:=Middle;
    y:=Mid;
    while x<Mid do
    begin
      if SortArray[y]<SortArray[x] then
      begin
        IntBackUp:=SortArray[y];
        Move(SortArray[x], SortArray[x+1], (y-x)*4);
        SortArray[x]:=IntBackUp;
        inc(y);
        inc(Mid)
      end;
      inc(x)
    end;
  end;
begin
  if not (Left=Right) then
  begin
    Middle:=(Left+Right) div 2;
    MergeSort(Left, Middle);
    MergeSort(Middle+1, Right);
    Merge
  end
end;

Anmerkung zum Quelltext: Irgendwo komme ich momentan auch außerhalöb des Speicherbereiches

. (Das problem löst sich sicherlich von alleine, wenn der Denkfehler raus ist

).

Gausi · Verfasst: Mi 01.03.06 21:04

Schlag mich, wenn ich jetzt Müll erzähle, aber so wie ich Mergesort kenne, ist das nicht ohne erhebliche Laufzeitverlängerung möglich (der Mischvorgang würde dann nicht mehr 2N Schritte brauchen (N zum Mischen, und weitere N zum Umkopieren), sondern bis maximal N^2 viele, da man ständig das Array komplett umbauen muss).

_________________
We are, we were and will not be.

Heiko · Beiträge: 3169 Erhaltene Danke: 11

Ich weiß nicht wie Move arbeitet, aber ich glaube das er nur N braucht (kopieren und dann das in das Zeil reinschreiben). Wenn beim kopieren bissl RAM gebraucht wird stört es ja nicht, aber alle Verfahren die ich finde kopieren alles neu in RAM

. Wir dürfen den Algo auch auf Zeigern umbasteln (wozu ich aber irgendwie nicht so richtig Lust habe), da doppelter Speicher (4*n Bytes für Daten + 4*n Bytes für die Zeiger)

.

Gausi · Verfasst: Do 02.03.06 16:09

Es ist schon richtig, dass einmal Move nur N Schritte braucht. Aber das muss man bei einem Merge-Vorgang ggf. N mal wiederholen (ich rede im O-Kalkül, konstante Faktoren spielen da keine Rolle).
Von daher fällt dieses Verfahren für eine "Optimierung" von Mergesort flach - da kann man dann direkt Bubblesort nehmen.

Ich habe das Problem "Merge ohne Hilfsarray" heute mal beim Mittagessen mit einer sehr netten Doktorandin an der Uni ausdiskutiert (die hat grade die Vorlesung Info3 hinter sich, wo auch Mergesort drankam). Wir sind dann zu dem Schluss gekommen, dass Mergesort ohne Hilfsarray auch ohne signifikante Steigerung der Laufzeit möglich ist (d.h. einmal Merge bleibt in O(N)). Allerdings ist der Verwaltungsaufwand der einzelnen Indizes (man braucht ein paar mehr als beim normalen mergen, wahrscheinlich 4 oder 5), immmens hoch und erfordert auch einige zusätzliche Vergleiche. Hinzu kommt, dass häufig nicht nur 2 Werte geswappt werden müssen, sondern 3, und ab und zu die Indizes selbst vertauscht werden müssen (also das i wird zu k und umgekehrt).

Das ganze ist dann unglaublich fehleranfällig für Indizierungsfehler, unübersichtlich und praktisch unmöglich nachvollziehbar. Selbst beim durchrechnen eines kleinen Beispiels an der Tafel (bzw. auf der Tür *g*) kommt man durcheinander, weil man diverse Fallunterscheidungen hat und sich diverse Markierungen merken muss.

Trotzdem bin ich mir nach anfänglichem Zweifel zu 90% sicher, das das möglich ist. Aber der Aufwand lohnt IMHO nicht. Wenn man ein schnelles In-Situ-Verfahren haben will, nimmt man Quick- oder Heapsort, die allerdings nicht so gut eine Vorsortierung ausnutzen können.

Frag mal deinen Lehrer, ob er weiß, was er da von dir verlangt. Wenn das dein Thema für deine Facharbeit ist und du dir ne 1++ verdienen willst, dann ist das ok - ansonsten nicht :roll:

.

Die Variante mit den Zeigern (d.h. anstelle der Arrays Listen zu nehmen [aber Vorsicht: Was in Delphi List heißt, ist oft eigentlich auch ein Array] ), ist natürlich eine Möglichkeit. Das Gegenargument hast du schon geliefert: Wenn man nur Integers sortieren möchte, ändert das am Speicherbedarf gar nichts - ob man nun jede Zahl doppelt speichert, oder für jede Zahl doppelten Platz benötigt - das ist Jacke wie Hose.

_________________
We are, we were and will not be.

Heiko · Beiträge: 3169 Erhaltene Danke: 11

Danke Gausie für die Zusatzinformationen (deinen Beitrag werde ich mal meinem Infolehrer zeigen, denn ich stimme dir voll zu, dass diese Optimierung ohne/mit Zeigern eigentlich sinnlos ist :mrgreen:

)

Heute im Mittagsband habe ichs dann hinbekommen

.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

procedure MergeSort(Left, Right: Integer);
var
  Middle: Integer;

  procedure Merge;
  var
    L: Integer;
    IntBackUp: Integer;
    Mid: Integer;
  begin
    Mid:=Middle+1;
    L:=Left;
    while (L<Mid) and (Mid<=Right) do
    begin
      if (SortArray[L]>SortArray[Mid]) then
      begin
        IntBackUp:=SortArray[Mid];
        Move(SortArray[L], SortArray[L+1], (Mid-L)*4);
        SortArray[L]:=IntBackUp;
        inc(Mid);
      end;
      inc(L)
    end
  end;
begin
  if Left<Right then
  begin
    Middle:=(Left+Right) div 2;
    MergeSort(Left, Middle);
    MergeSort(Middle+1, Right);
    Merge
  end
end;

Horst_H · Verfasst: Fr 03.03.06 09:08

Hallo,

hast Du mal einen Zaehler eingebaut, wieviele Byte da verschoben werden.
Also die Summe

markieren

Delphi-Quelltext

1:
2:
3:

Move(SortArray[L], SortArray[L+1], (Mid-L)*4);   
Summ := summ+(Mid-L)
SortArray[L]:=IntBackUp;

Wenn die Daten genau umgekehrt sortiert sind, ist Mid-L= konstant= halbe Abschnittbreite und das (Mid-L)-fach, also (Mid-l)^2 Einzelwert Kopierungen, das ist ja wohl nicht im Sinne des Erfinders.
Den Fall kann man einfach testen:

markieren

Delphi-Quelltext

1:
2:

If(SortArray[L]> SortArray[R]) then
  Daten sind umgekehrt.

Gruss Horst
P.S.
Ich mit mergesort unter Punkt c aus www.inf.fh-flensburg...eren/merge/merge.htm sehr gute Erfahrungen gemacht, da hier nur die halbe Zeigerliste kopiert werden muss und weniger Fallunterscheidungen noetig sind.
Insbesondere bei Zeigerlisten auf groessere Strukturen(>10 Byte ;-)

) und Millionen von Datensaetzen ist es von Vorteil, das Mergesort zu Beginn immer im Speicher sehr nahe Elemente vergleicht, waehrend Quicksort die Daten schon sofort sehr durcheinanderwirbelt, sodass die Vergleiche entsprechend lange auf den Hauptspeicher warten muessen.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:

program untitled;
{$APPTYPE CONSOLE}
uses
  sysutils;

type
  TPointerList = array of Pointer;
  TCompFunc = function(A,B:Pointer):integer;
  //Hier wird die Pointerliste direkt fuer Integer Werte missbraucht

function intComp(A,B:Pointer):integer;
begin
  result := (integer(A)-integer(B));
end;

procedure mergesort(lks,rts:integer;a: TPointerList;CompFunc:TCompFunc);
var
  B : TPointerlist;
  procedure merge(links,rechts:integer);
  var
    i,j,k,mid :integer;

    procedure InsertSort;
    var
      i: integer;
      Pivot : Pointer;
    begin
      for i:=links+1 to rechts do
        begin
        j :=i;
        Pivot := A[j]; // elemente merken
        while (j>links) AND (CompFunc(A[j-1],Pivot)>0) do
          begin  // pruefen, ob das gemerkte element kleiner als das betrachtete ist
          A[j] := A[j-1];// und gegebenenfalls austauschen
          dec(j);
          end;
        A[j] :=Pivot;// s.o.
        end;
     end;

  begin
    If rechts-links<=4 then
      //by kleinen Abschnitten Mengen insertion sort
      InsertSort
    else
      begin
      // Mittleres Element bestimmen und rekursiver Abstieg
      mid := (rechts+links) div 2;
      merge(links, mid);
      merge(mid+1, rechts);
      //schon sortiert?
      IF CompFunc(A[Mid],A[Mid+1])<0 then
        exit;
      // Mischen der sortierten Unterfelder
      // dabei wird ein Hilfsfeld b verwendet
      // Daten in Hilfsfeld kopieren
      move(A[links],B[0],(mid-links+1)*SizeOf(Pointer));
      i := 0;
      j := mid+1;
      k := links;
      while (k<j) AND (j<=Rechts) do
        begin
        IF CompFunc(B[i],A[j])<=0 then
          begin
          A[k] := B[i];
          inc(i);
          end
        else
          begin
          A[k]:= A[j];
          inc(j);
          end;
        inc(k);
        end;

      while (k<j) do
        begin
        A[k] := B[i];
        inc(i);
        inc(k);
        end;
    end;   // Ende von "if" (Abbruchbedinung)
  end;     // Ende von "procedure"
begin
  setlength(B,((rts-lks)+1)div 2);
  merge(lks,rts);
  setlength(B,0);
end;

Var
  T0,T1: TDateTime;
  A : TPointerlist;
  i,k : integer;
Begin
  randomize;
  k := 10000000;
  setlength(A,K);
  For i := 0 to K-1 do
    begin
    A[i]:= Pointer(random(k));
    end;

  T0:= time;
  mergesort(0,High(A),A,intComp);
  T1 := time;
  Writeln( FormatDateTime('hh:mm:ss.zzz',T1-t0));
  readln;
end.

EDIT: Eine hoffentlich funktioniernde Version.
Mit k = 10.000.000 dauert das natürlich ein paar Sekunden, auch schon wegen der Zufallszahlen

Gausi · Verfasst: Fr 03.03.06 17:26

Auch wenns vielleicht nicht mehr unbedingt interessiert: Das Verfahren, was ich gestern im Kopf hatte, funktioniert so nicht. Ich war heute nochmal Mittagessen, und da haben wir das weiter diskutiert.
Die Grundidee des Verfahrens ist, dass man den Platz, wo Elemente aus dem rechten Teilarray nach vorne verschoben werden, zur Speicherung von Elementen des linken Teilarrays nutzt. Damit die Vorsortierung nicht verloren geht, muss man dafür das rechte Teilarray splitten, sodass das Gesamt-Array sich im Verlauf so aufteilt:

markieren

Quelltext

1:	\|--X--\|----L2----\|----R1----\|---L1---\|---R2--\|

Dabei ist X das bereits sortierte Teilstück, L1--L2 der Rest des linken sortierten Arrays (Achtung: verkehrte Reihenfolge!), und R1--R2 das rechte Teilarray. Die "Vergleichs-Zeiger" stehen dabei am Anfang von L1 bzw. R1.
Man bekommt nun ein Problem, wenn R1[1] nach vorne geschoben muss. Dann muss man entweder einen der Blöcke komplett verschieben (L2), oder aber je zwei der Blöcke rekursiv mergen, sodass man wieder bei der Ursprungssituation

markieren

Quelltext

1:	\|--XX--\|--L--\|--R--\|

ist, und man die Blöcke wieder neu aufteilen kann. Wir vermuten, dass man das mit Hilfe einer amortisierten Laufzeitabschätzung auf Linearzeit runterdiskutieren kann (zumindest im mittleren Fall, im Worst-Case habe ich noch leichte Zweifel). Es scheint sinnvoll zu sein, bei "kleinen Blöcken" eine Verschiebung vorzunehmen, und erst bei größeren Blöcken rekursiv zu mergen. Wo da die optimale Grenze liegt, dürfte aus der Laufzeitanalyse hervorgehen.
Das aber wiederrum war uns dann zu blöd, und haben uns lieber über das Wetter unterhalten :lol:

. Amortisierte Laufzeitabschätzung ist aber auch irgendwie "bäh".

Und mir kam dabei ein Zitat aus StarTrek in den Kopf. Ich glaube, es kommt aus der Folge, in der die Sheliak-Corporation einen Planeten besiedeln will, auf der widerrechtlich eine Menschen-Kolonie ist, wo man aber nicht beamen kann.

Geordi LaForge meint dann gegen Ende:

Captain, wir können es schaffen. Wir brauchen nur drei Jahre Entwicklungszeit und ca. 150 Techniker und Ingenieure, aber wir können es schaffen...

_________________
We are, we were and will not be.

uall@ogc · Verfasst: Fr 03.03.06 18:10

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:

1. einfache annahme:

1 3 4 5 | 6 7 8 9
z1      | z2

z1^ und z2^ vergleichen da z1^ < z2^ immer inc(z1)
bei z1 = z2 dann ende

Resultat:

1 3 4 5 | 6 7 8 9
          z1
          z2
_______________________

2. annahme (bsp):

1 3 4 8 | 2 2 2 2
z1        z2

1. schritt
z1^ < z2^ -> inc (z1)

1 3 4 8 | 2 2 2 2
  z1      z2

2. schritt
z1^ > z2^ -> mov z1^ <> z2^, inc(z1), inc(z2)

1 2 4 8 | 3 2 2 2
    z1      z2

wiederhole bis z1 = z2


(ich führ das mal vor)

1 2 2 8 | 3 4 2 2
      z1      z2

1 2 2 2 | 3 4 8 2
          z1    z2

1 2 2 2 | 2 4 8 3
            z1  z2

1 2 2 2 | 2 3 8 4
              z1z2

1 2 2 2 | 2 3 4 8
                z1
                z2 (ende)

wenn z2 = max dann z2 nicht mehr erhöhen!

O(n) da z1 maximal n schritte hat
aber wenn sortiert dann O(n/2) also auch o(n)

Einwände? Fehler? (Wenn ja mit Bsp wo es nicht funzt)

uall@ogc · Verfasst: Fr 03.03.06 18:28

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

procedure merge(list: array of integer; min, max: integer);
var i, j, a: integer;
begin
  i := min;
  j := max div 2;
  while i < j do
  begin
    if (list[i]) > list[j]) then
    begin
      a := list[i];
      list[i] := list[j];
      list[j] := a;
      if (j < max) then inc(j);
    end;
    inc(i);
  end;
end;

ungetestet

list ist z.b. ein array: 1 2 3 4 | 2 2 2 9 | 3 3 3 3 | 1 2 7 8
wobei 2 mal aufgerufen wird mit

merge(list,0,

;
merge(list,9,17);

wenn low(list) = 0

für den Mergesort dann in etwa so

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

procedure mergesort(list: array of integer);
var : integer;
begin
  i := 2;
  while i < high(list) do
  begin
    for j := 0 to high(list) div i do
      merge(list,j*i,j*i+i);
    i := i*2;
  end; 
end;

Ungetestet und würde im Moment auch nur so mit Listen der größe n^2 funktionieren.
Hab leider kein funktionierendes Delphi sonst würd ich des mal selbst testen.

_________________
wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit

Gausi · Verfasst: Fr 03.03.06 18:37

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

     20 30 70 90 |   1    2   50   60 61 62 63
     --             --

-->   1 30 70 90 |  20 |  2   50   60 ...
                    --   --

-->   1  2 70 90 |  20   30 | 50   60 ..
                    --        --

-->   1  2 20 90 |  70   30 | 50   60  FEHLER
Abhilfe: Rechtes Array aufsplitten
-->   1  2 20 90 | 50 |  30   70 | 60 61...
                   --    --

Bis dahin ist das jede einzelne Zeile in konstanter Zeit durchführbar. Aber hier bekommt man ggf. später Probleme. Dafür Beispiele zu finden, ist aber etwas komplizierter, die werden dann etwas länger und unübersichtlich.
Das nur mit Code und Bildern zu erklären, ist zu umständlich, das muss man eher an der Tafel vorführen. Aber es geht nicht so ohne weiteres - das garantiere ich dir ;-)

_________________
We are, we were and will not be.

uall@ogc · Verfasst: Fr 03.03.06 19:02

Hast recht habs nochmal eben getestet.

Kommt man auf ein Laufzeitverhalten im WorstCase von O(n^2 / 4) [O(n^2)]und BestCase O(n/2) [O(n)]

_________________
wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit

Gausi · Verfasst: Fr 03.03.06 19:13

uall@ogc hat folgendes geschrieben:

Kommt man auf ein Laufzeitverhalten im WorstCase von O(n^2 / 4)

Die Schritte, die ich in meinem Beispiel durchgeführt habe, gehen insgesamt in O(N). Ab und an wird ein rekursiver Merge nötig, mit einem wesentlich kleinerem Array. Meine (und Antjes) Vermutung ist, dass man durch eine geeignete "Kontostandsfunktion" genug Zeit bei den einfachen Operationen "ansparen " kann, so dass dieses Merge dann davon "bezahlt" werden kann, um innerhalb von O(N) zu bleiben.
Das basiert auf keiner exakter Analyse, sondern auf Bauchgefühl, kann also auch gut verkehrt sein.

Aber das bewegt sich weit abseits des Schulniveaus...

_________________
We are, we were and will not be.

uall@ogc · Verfasst: Fr 03.03.06 19:19

Fragt man sich nun ob im rechten Teil nicht noch kompliziertere Sachen auftreten können (d.h. mehrmals unterteilt)
für dne linkten Teil braucht man O(n/2), um den Rechten (ggf) wieder herzustellen, reicht ein simpler Bubblesort der in dem Fall immer einen bestCase von O(n/2) hat.
Das liegt daran, dass das Element im schlimmsten Fall weietr nach hinten verschoben werden muss.

Du musst bei derin Methode halt ziemlich viel merken. Und bei einer weiteren Splittung (die ja eventl auftreten kann, bei 4er Pärchen merkt man das ja nicht) funkioniert es nicht und du musst ebenfalls (wie shcon gesagt) einen Rekursiven Merge machen

_________________
wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit

Gausi · Verfasst: Fr 03.03.06 19:39

Doch, man kann merken, wann eine weitere Splittung des rechten Teils nötig wird: Wenn bereits gesplittet ist, und das kleinste Element des rechten Arrays kleiner ist als das Linke. Dann muss man entweder das linke Linke eins nach rechts verschieben (wenn da wenig Elemente drin sind), oder halt die 4 Teilblöcke zu 2 mergen.
Ich kann leider nicht auf Anhieb genau abschätzen, inwieweit durch das neue Mergen die Vorsortierung vor- oder nachteilhaft für den Gesamtmerge wird (ich investiere da auch keine Energie rein, da es nichts bringt ;-)

)

BubbleSort etc. braucht man imho nicht, da das Verfahren die Vorsortierung in den maximal 4 Teilblöcken erhält.

_________________
We are, we were and will not be.

Heiko · Beiträge: 3169 Erhaltene Danke: 11

Gausi hat folgendes geschrieben:

Aber das bewegt sich weit abseits des Schulniveaus...

Das stört micht nicht, im Gegenteil. Was wir in der Schule machen langweilt mich meistens eher :gaehn:

(zu mindestens von der Praxis her).

@Bubbelsort: Eine Bubbelsort verschlechtert doch die Performance eigentlich in der Mergesort erheblich, da dadurch der Vorteil der vorsortierer wegfällt. Oder habe ich einen part bei euch gerade vergessen? :gruebel:

(schnelleres als Mergesort habe ich eigentlich bisher noch nicht gemacht, wodurch ich nicht alles beurteilen kann

).

Gausi · Verfasst: Fr 03.03.06 20:35

Heiko hat folgendes geschrieben:

@Bubbelsort: Eine Bubbelsort verschlechtert doch die Performance eigentlich in der Mergesort erheblich, da dadurch der Vorteil der vorsortierer wegfällt. Oder habe ich einen part bei euch gerade vergessen? :gruebel:

(schnelleres als Mergesort habe ich eigentlich bisher noch nicht gemacht, wodurch ich nicht alles beurteilen kann

).

Man kann schnell sortieren, und langsam. In aller Regel langsam (d.h. im Mittel eine Laufzeit von N^2) sind Sortieren durch Auswahl, Sortieren durch Einfügen, Bubblesort, Shakersort. Schnelle Varianten (d.h. im Mittel log(N) * N Laufzeit) sind Mergesort in den unterschiedlichen Varianten, Heapsort und Quicksort. Letzterer ist besonders interssant, da er im schlechtesten Fall genauso lange wie Bubblesort braucht, aber in der Praxis sich als der schnellste herausgestellt hat.

Es gibt auch Verfahren, die in Linearzeit sortieren (Bucketsort), aber diese Verfahren arbeiten dann unter anderen Voraussetzungen (nicht nur "a < b", sondern greifen z.B. auf die einzelnen Ziffern der Zahl zu).

Von daher stimmt deine Aussage, dass es prinzipiell nichts (prinzipiell) schnelleres als Mergesort gibt.

Was ich hier mit diskutiert habe ist, ob es eine Möglichkeit gibt, den Nachteil des zusätzlichen Speicherbedarfs von Mergesort auszubügeln, ohne den Geschwindigkeitsvorteil einzubüßen, was bei deiner Lösung mit Move leider der Fall ist. Es scheint zu gehen, ist aber recht kompliziert und lohnt nicht wirklich (das StarTrek-Zitat trifft es ganz gut, finde ich).

_________________
We are, we were and will not be.

Delphi-Laie · Verfasst: Di 08.09.09 14:55

Heiko hat folgendes geschrieben :

MergeSort [...] mit einer kleinen Optimierung, wozu ich bei Google etc. bisher nichts gefunden habe : [...] kein Hilfsarray beim "mergen" (mischen) verwenden.

3,5 Jahre nach dem Originalbeitrag hat sich inzwischen etwas getan: Es findet sich im Internet ein Mergesort eines Österreichers Siegfried Sielaff, das er Swapsort nennt und diese Bedingung zu erfüllen scheint. Der Autor beschreibt einleitend über mehrere Absätze (s)ein Verfahren, was eigentlich im wesentlichen die Grundidee von Mergesort ist. Setzt man das Ockhamsche Rasiermesser an, dann bleibt das "in-place"-Vermischen als wirklich seine Leistung dazu übrig. Der Algorithmus ist allerdings nicht ganz trivial und fragil: Wehe, wenn nur eine Variable nicht richtig gesetzt/begrenzt wird. Die Grundidee habe ich verstanden, jedoch das, was er dazu als Algorithmus anbietet, in/mit Delphi bisher noch nicht zum Laufen gebracht. Vielleicht versuche ich es mit dem eigenen Schreiben. Gerade beim Mischen vieler, kleiner Teilarrays, was beim Mergesort ja weit überwiegend passiert, wird der Algorithmus ziemlich fummelig und rechenintensiv (Gausi führte dazu auch schon einiges aus, was ich anhand erster Erfahrungen dazu nur bestätigen kann), so daß ich - im Gegensatz zum Autor, der das natürlich im rosigen Licht verkauft - nicht so recht an eine Laufzeitgleichwertigkeit mit dem "echten" Mergesort glauben mag.

Gausi · Verfasst: Di 08.09.09 15:15

Dazu möchte ich auf eine Arbeit von 1988 verweisen, auf die ich vor ein paar Monaten gestoßen bin:

portal.acm.org/citation.cfm?id=42392.42403

Nennt sich "Practical In-Place Merging". Vorgestellt wird da schon ein Linearzeit-Mischen auf konstantem Platz, was durchaus praktikabel ist. Getestet habe ich das nicht, das Verfahren ist auch nicht "mal eben so runterprogrammiert", aber auch nicht furchtbar komplex. Wie die Arbeit von Herrn Sielaff dazu einzuordnen ist, weiß ich nicht. Aber: wie man effizient (d.h. Linearzeit) auf konstantem Platz mergen kann, ist jetzt nicht soo neu. (Die Arbeit kannte ich 2006 aber noch nicht. )

(Der Link ist normalerweise kostenpflichtig. Ob es die Arbeit woanders kostenfrei gibt, weiß ich nicht - aus universitären Netzen hat man in der Regel Zugriff darauf. ;-)

)

_________________
We are, we were and will not be.

Delphi-Laie · Verfasst: So 27.09.09 17:24

Peter Weigel stellte auf (s)einer Internetseite www.sortieralgorithmen.de und, nachdem er sie vor wenigen Jahren abgab und diese seit Monaten nicht mehr erreichbar ist, dankenswerterweise nunmehr wieder unter home.arcor.de/peter-...orithmen/bitonicsort u.a. ein Verfahren vor, daß er Bitonic Sort nennt (nicht zu verwechseln mit Bitonic Mergesort, einem "echten", also "out-of-place"-Mergesort), das (rekursiv, und zwar "depth first") "in place" mischt. Großer Nachteil: Es funktioniert nur mit Elementeanzahlen, die gleich einer Zweierpotenz sind.

Gausi · Verfasst: So 27.09.09 17:36

Hm, Bitonicsort kenne ich eigentlich nur als paralleles Sortierverfahren in Sortiernetzen. Da wird der Algorithmus quasi in Hardware gegossen. Damit ist dann sortieren schneller als O(n) möglich. Wenn man die Dinger sequentiell nachbaut, kann evtl. auch was nettes bei rauskommen - hier wohl O(n log(n)^2). :nixweiss:

en.wikipedia.org/wiki/Sorting_network
en.wikipedia.org/wiki/Bitonic_sorter

_________________
We are, we were and will not be.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme