mergesort

sveno · Beiträge: 40

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?

markieren

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;

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:

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 · Verfasst: Mo 24.01.05 12:32

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

Und noch ein paar Kommentare zum Quellcode

markieren

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

_________________
We are, we were and will not be.

sveno · Beiträge: 40

Ja, das stimmt, werd ich gleich ma entfernen, danke. Aber trotzdem läuft das Prog dann nicht:(

Die Fehlermeldung ist ein Stack Überlauf. Aber ich finde den Fehler einfach nicht

Gausi · Verfasst: 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:

markieren

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.

_________________
We are, we were and will not be.

sveno · Beiträge: 40

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:

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 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 · Verfasst: Mo 24.01.05 16:20

probiers mal hiermit

markieren

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

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:

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 · Beiträge: 40

Gausi hat folgendes geschrieben:

markieren

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.

sveno · Beiträge: 40

markieren

Delphi-Quelltext

1:
2:

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

Das hat auch nicht geholfen, immer noch stack überlauf

st-matze · Verfasst: Mo 24.01.05 17:52

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

markieren

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 · Beiträge: 40

Meinst du so:

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 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 · Verfasst: Mo 24.01.05 18:01

kleine optimierung

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:

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 · Beiträge: 40

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

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

sveno · Beiträge: 40

www.beepworld.de/mem...19/sveno2/bubble.rar

Das ist der Link zum Download meines Progs, denke so ist es einfacher einen Fehler zu finden.

Gruss Sven

Gausi · Verfasst: 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:

markieren

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

_________________
We are, we were and will not be.

sveno · Beiträge: 40

Jetzt müsste der Download gehen.

Der Fehler ist immer noch ein Stack Überlauf.

Gausi · Verfasst: Mo 24.01.05 23:10

markieren

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.

_________________
We are, we were and will not be.

sveno · Beiträge: 40

Gausi hat folgendes geschrieben:

markieren

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.

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

Gausi · Verfasst: Mo 24.01.05 23:25

Dann tu uns noch den Gefallen und markiere den Thread als gelöst, wenn wirklich alles klar ist.

_________________
We are, we were and will not be.

Schnitzelll · Hält's aus hier Beiträge: 1 XP

markieren

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme