Entwickler-Ecke :: Thema anzeigen

sveno - So 23.01.05 21:56
Titel: mergesort

Hallo.

Habe versucht den mergesort zu programmieren, aber es klappt nicht. Eine und 2 Zahlen sortiert er noch korrekt, aber sobald die Gröse der zu sortierenden Zahlen grösser als 2 ist bricht Delphi ab. Weiss jemand woran das liegt?

Delphi-Quelltext

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

procedure TFrmbubble.btmergeClick(Sender: TObject);
var zeit, start: integer;
    cursor: TCursor;
begin
 cursor := screen.Cursor;
 Screen.Cursor := crHourGlass;
 try
  start := 1;
  sortfeld := zufallsfeld;
  starte_zeit(Zeit);
  merge_sort(start,anzahl);
  stoppe_zeit(Zeit);
  anzahl := SpEdAnzahl.Value;
  kopieresortfeldzustrgrd;
  lbmsmerge.caption := inttostr(Zeit);
 finally
 Screen.Cursor := cursor;
 end;
end;

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:

procedure merge_sort(var anfang, ende: integer);
var hilfsfeld: TFeld;
    i,x,y,anfangrechts,endelinks: integer;
begin
 IF (ende-anfang) <> 0 THEN
 begin
  IF anfang mod 2 = 1 THEN endelinks := (ende DIV 2) ELSE endelinks := (ende DIV 2) + 1 ;
  anfangrechts := endelinks + 1;

  merge_sort(anfang,endelinks);

  merge_sort(anfangrechts,ende);

  IF anfang mod 2 = 1 THEN endelinks := (ende DIV 2) ELSE endelinks := (ende DIV 2) + 1 ;
  anfangrechts := endelinks + 1;
  x := 0;
  y := 0;
  FOR i := Anfang TO ende DO
  begin
   IF sortfeld[anfang + x] < sortfeld[anfangrechts + y] THEN
   begin
    hilfsfeld[i] := sortfeld[anfang + x];
    sortfeld[anfang + x] := 1001;
    IF x < (endelinks - anfang) THEN inc(x);
   end ELSE
   begin
    hilfsfeld[i] := sortfeld[anfangrechts + y];
    sortfeld[anfangrechts + y] := 1001;
    IF y < (ende - anfangrechts) THEN inc(y);
   end;
  end;
  FOR i := anfang TO ende DO
   sortfeld[i] := hilfsfeld[i];
 end;
end;

Gausi - Mo 24.01.05 12:32

Gegenfrage: Was passiert denn genau? Was kommt für eine Fehlermeldung?

Und noch ein paar Kommentare zum Quellcode

Delphi-Quelltext

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

procedure merge_sort(var anfang, ende: integer);
// lass das var mal weg...
var hilfsfeld: TFeld;
    i,x,y,anfangrechts,endelinks: integer;
begin
 IF (ende-anfang) <> 0 THEN
 begin
  IF anfang mod 2 = 1 THEN endelinks := (ende DIV 2) ELSE endelinks := (ende DIV 2) + 1 ;
  anfangrechts := endelinks + 1;
//warum so kompliziert?
// mitte:= (anfang+ende) DIV 2
// mergesort(anfang, mitte);
// mergesort(mitte+1,ende);

  merge_sort(anfang,endelinks);
  merge_sort(anfangrechts,ende);

  IF anfang mod 2 = 1 THEN endelinks := (ende DIV 2) ELSE endelinks := (ende DIV 2) + 1 ;
  anfangrechts := endelinks + 1; 
// ... dann musst du das hier nicht neu berechnen
[...]

Gausi - Mo 24.01.05 15:38

Stacküberlauf? Hab ich mir doch gedacht. :roll:

Fehler ist der folgende: Du berechnest die neuen Grenzen falsch. Geh das mal am Beispiel 4 durch:

Quelltext

1:
2:
3:
4:
5:
6:
7:

mergesort(1,4) liefert die beiden rekursiven Aufrufe
    Mergesort(1,2) und
        (läuft glatt durch)
    Mergesort(3,4)
        endelinks = 4 DIV 2 = 2
        anfangrechts = 2+1 = 3
        Mergesort(3,2)

Dieser Aufruf führt offensichtlich in eine Endlosrekursion, bis irgendwann der Stack überläuft.

Wie es richtig geht, hab ich oben schon als Kommentar gepostet.

sveno - Mo 24.01.05 16:18

Vielen Dank für deine Hilfe, den Fehler hab ich nun behoben:)
Aber er eigt immer noch einen Stack Überlauf an. :cry:

Ich habs inzwischen so verändert:

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 merge_sort(var anfang, ende: integer);
var hilfsfeld: TFeld;
    i,x,y,anfangrechts,endelinks: integer;
begin
 IF (ende-anfang) <> 0 THEN
 begin
  endelinks := ((ende - anfang) DIV 2) + anfang;
  anfangrechts := endelinks + 1;

  merge_sort(anfang,endelinks);

  merge_sort(anfangrechts,ende);

  x := 0;
  y := 0;
  FOR i := Anfang TO ende DO
  begin
   IF sortfeld[anfang + x] < sortfeld[anfangrechts + y] THEN
   begin
    hilfsfeld[i] := sortfeld[anfang + x];
    sortfeld[anfang + x] := 1001;
    IF x < (endelinks - anfang) THEN inc(x);
   end ELSE
   begin
    hilfsfeld[i] := sortfeld[anfangrechts + y];
    sortfeld[anfangrechts + y] := 1001;
    IF y < (ende - anfangrechts) THEN inc(y);
   end;
  end;
  FOR i := anfang TO ende DO
   sortfeld[i] := hilfsfeld[i];
 end;
end;

*EDIT*

Hab jetzt erst deine Verbesserung in deinem ersten Port gesehen, ich werds gleich mald amit ausprobieren.

st-matze - Mo 24.01.05 16:20

probiers mal hiermit

Delphi-Quelltext

1:
2:

  IF ende > anfang THEN 
// IF (ende-anfang) <> 0 THEN

ansonsten hier auch mal ein komplettvorschlag von mir

a ist das zu sortierende array
b ist das hilfsarray

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:

procedure merge(lo,m,hi:integer);
var
  i,j,k:  integer;
begin
  i:=0;j:=lo;
  while (j <= m) do
  begin
    b[i]:=a[j];Inc(i);Inc(j);
  end;
  i:=0; k:=lo;
  while (k<j) and (j<= hi) do
  begin
    if (b[i]<=a[j]) 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(k); inc(i);
  end;
end;

procedure mergesort (lo,hi:integer);
var
  m:  integer;
begin
  if lo < hi then
  begin
    m :=  (lo + hi) div 2;
    mergesort(lo,m);
    mergesort(m+1,hi);
    merge(lo,m,hi);
  end;
end;

zum sortieren wird dann natürlich
mergesort
mit den indizes 0 und high(a) aufgerufen.

sveno - Mo 24.01.05 16:29

Gausi hat folgendes geschrieben:

Delphi-Quelltext

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

//warum so kompliziert?
// mitte:= (anfang+ende) DIV 2
// mergesort(anfang, mitte);
// mergesort(mitte+1,ende);

  merge_sort(anfang,endelinks);
  merge_sort(anfangrechts,ende);

  IF anfang mod 2 = 1 THEN endelinks := (ende DIV 2) ELSE endelinks := (ende DIV 2) + 1 ;
  anfangrechts := endelinks + 1; 
// ... dann musst du das hier nicht neu berechnen
[...]

Wenn ich dass so mache, dann krieg ich die fehlermeldung "die typen der tatsächlichen und formalen Var - Parameter müssen übereinstimmen.

Einen komplett vorschlag möcht ich nicht nehmen, mir gehts ja nicht darum den megre sort zu haben, mir gehts darum das ich ihn selbst programmieren kann und dabei delphi lerne.

st-matze - Mo 24.01.05 17:52

funktioniert wunderbar, wenn du den var parameter auch entfernst.
dann kommt die fehlermeldung auch nicht.

Delphi-Quelltext

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

procedure merge_sort({var} anfang, ende: integer);
var hilfsfeld: TFeld;
    i,x,y,anfangrechts,endelinks: integer;
begin
// IF (ende-anfang) <> 0 THEN
  if ende > anfang then
 begin
  endelinks := ((ende - anfang) DIV 2) + anfang;
  anfangrechts := endelinks + 1;
  merge_sort(anfang,endelinks);
  merge_sort(anfangrechts,ende);
  x := 0;
  y := 0;
  FOR i := Anfang TO ende DO
{usw...}

aus performance gründen soltest du hilfsfeld global definieren.
ansonsten brauchst du bei größeren sortier vorgängen extrem viel speicher.

sveno - Mo 24.01.05 18:00

Meinst du so:

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 merge_sort(anfang, ende: integer);
var hilfsfeld: TFeld;
    i,x,y,mitte, mitterechts: integer;
begin
 IF ende > anfang THEN
 begin
  mitte := (anfang + ende) DIV 2;
  mitterechts := mitte + 1;

  merge_sort(anfang,mitte);

  merge_sort(mitterechts,ende);

  x := 0;
  y := 0;
  FOR i := Anfang TO ende DO
  begin
   IF sortfeld[anfang + x] < sortfeld[mitterechts + y] THEN
   begin
    hilfsfeld[i] := sortfeld[anfang + x];
    sortfeld[anfang + x] := 1001;
    IF x < (mitte - anfang) THEN inc(x);
   end ELSE
   begin
    hilfsfeld[i] := sortfeld[mitterechts + y];
    sortfeld[mitterechts + y] := 1001;
    IF y < (ende - mitterechts) THEN inc(y);
   end;
  end;
  FOR i := anfang TO ende DO
   sortfeld[i] := hilfsfeld[i];
 end;
end;

Dann kommt aber bei mir immer noch Stack Überlauf.

st-matze - Mo 24.01.05 18:01

kleine optimierung

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:

procedure merge_sort({var} anfang, ende: integer);
var hilfsfeld: TFeld;
    i,x,y,anfangrechts,endelinks: integer;
begin
// IF (ende-anfang) <> 0 THEN
 if ende > anfang then
 begin
//  endelinks := ((ende - anfang) DIV 2) + anfang;
  endelinks :=  (ende + anfang) div 2;
  anfangrechts := endelinks + 1;
  merge_sort(anfang,endelinks);
  merge_sort(anfangrechts,ende);
//  x := 0;
//  y := 0;
  x := anfang;
  y := anfangrechts;
  FOR i := Anfang TO ende DO
  begin
   IF sortfeld[{anfang + }x] < sortfeld[{anfangrechts + }y] THEN
   begin
    hilfsfeld[i] := sortfeld[{anfang + }x];
    sortfeld[{anfang + }x] := 1001;
    IF x < (endelinks{ - anfang}) THEN inc(x);
   end ELSE
   begin
    hilfsfeld[i] := sortfeld[{anfangrechts + }y];
    sortfeld[{anfangrechts + }y] := 1001;
    IF y < (ende{ - anfangrechts}) THEN inc(y);
   end;
  end;
  FOR i := anfang TO ende DO
   sortfeld[i] := hilfsfeld[i];
 end;
end;

hinweis: ab tausend und nen paar zerquetschten spielt der stackspeicher von rechner aber nicht mehr mit. weil zu viele rekursionen.

st-matze

sveno - Mo 24.01.05 18:14

Funktioniert das denn so bei dir? Wenn ja muss bei mir ja immernoch irgendwo ein Fehler drin sein. habs jetzt so:

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 merge_sort(anfang, ende: integer);
var hilfsfeld: TFeld;
    i,x,y,mitte, mitterechts: integer;
begin
 IF ende > anfang THEN
 begin
  mitte := (anfang + ende) DIV 2;
  mitterechts := mitte + 1;

  merge_sort(anfang,mitte);

  merge_sort(mitterechts,ende);

  x := anfang;
  y := mitterechts;
  FOR i := Anfang TO ende DO
  begin
   IF sortfeld[x] < sortfeld[y] THEN
   begin
    hilfsfeld[i] := sortfeld[x];
    sortfeld[x] := 1001;
    IF x < mitte THEN inc(x);
   end ELSE
   begin
    hilfsfeld[i] := sortfeld[y];
    sortfeld[y] := 1001;
    IF y < ende THEN inc(y);
   end;
  end;
  FOR i := anfang TO ende DO
   sortfeld[i] := hilfsfeld[i];
 end;
end;

Danke für die Optimierung, ist so gleich viel übersichtlicher

Gausi - Mo 24.01.05 21:56

Kann ich nicht downloaden...

Was kommt denn für ein Fehler? Ich hab grade deine letzte Version kopiert, und etwas drumrum geschrieben:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

for i:=1 to 30 do
    sortfeld[i]:=random(100);
merge_sort(1, 30);
memo1.Lines.add('Mergesort:');
for i:=1 to 30 do
    memo1.lines.Add(inttostr(sortfeld[i]));

Und das Ergebnis sah ziemlich sortiert aus...

Gausi - Mo 24.01.05 23:10

Delphi-Quelltext

1:	TFeld = Array[1..100000] of integer;

kann man machen. Aber warum kein dynamisches Array?

Problem ist, dass du in jedem rekursiven Aufruf von Mergesort ein Array mit 100.000 Einträgen als Variable hast. Das scheint nicht auf den Stack zu passen. Nimm als Hilfsfeld eine globale Variable, dann gehts.

sveno - Mo 24.01.05 23:19

Gausi hat folgendes geschrieben:

Delphi-Quelltext

1:	TFeld = Array[1..100000] of integer;

JAAAAA! Das wars, es läuft endlich! DAAANKE!! :D :D :D

Schnitzelll - Mi 26.01.05 23:21

Delphi-Quelltext

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

{...}
  begin
   IF sortfeld[x] < sortfeld[y] THEN
   begin
    hilfsfeld[i] := sortfeld[x];
    sortfeld[x] := 1001;
    IF x < mitte THEN inc(x);
   end ELSE
   begin
    hilfsfeld[i] := sortfeld[y];
    sortfeld[y] := 1001;
    IF y < ende THEN inc(y);
   end;
  end;
  FOR i := anfang TO ende DO
   sortfeld[i] := hilfsfeld[i];
 end;
end;

...

warum muss da der Wert auf 1001 gesetzt werden? gibt es da keine andere (bessere) möglichkeit???

Moderiert von raziel: Delphi-tag repariert und Highlight-Tag hinzugefügt

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!