Autor |
Beitrag |
sveno
Beiträge: 40
|
Verfasst: So 23.01.05 21:56
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; |
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
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
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
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); 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; [...] |
_________________ We are, we were and will not be.
|
|
sveno
Beiträge: 40
|
Verfasst: Mo 24.01.05 15:08
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
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mo 24.01.05 15:38
Stacküberlauf? Hab ich mir doch gedacht.
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.
_________________ We are, we were and will not be.
|
|
sveno
Beiträge: 40
|
Verfasst: 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.
Ich habs inzwischen so verändert:
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.
Zuletzt bearbeitet von sveno am Mo 24.01.05 16:21, insgesamt 1-mal bearbeitet
|
|
st-matze
Beiträge: 138
Win 3.11, Win 95, Win 98, Win XP
D7 Ent, D6 Pers, (D5 Pers)
|
Verfasst: Mo 24.01.05 16:20
probiers mal hiermit
Delphi-Quelltext 1: 2:
| IF ende > anfang THEN |
ansonsten hier auch mal ein komplettvorschlag von mir
a ist das zu sortierende array
b ist das hilfsarray
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
|
Verfasst: Mo 24.01.05 16:29
Gausi hat folgendes geschrieben: |
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| 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; [...] | |
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
|
Verfasst: Mo 24.01.05 16:33
Delphi-Quelltext 1: 2:
| IF ende > anfang THEN |
Das hat auch nicht geholfen, immer noch stack überlauf
|
|
st-matze
Beiträge: 138
Win 3.11, Win 95, Win 98, Win XP
D7 Ent, D6 Pers, (D5 Pers)
|
Verfasst: 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( anfang, ende: integer); var hilfsfeld: TFeld; i,x,y,anfangrechts,endelinks: integer; begin 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 |
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
|
Verfasst: Mo 24.01.05 18:00
Meinst du so:
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
Beiträge: 138
Win 3.11, Win 95, Win 98, Win XP
D7 Ent, D6 Pers, (D5 Pers)
|
Verfasst: Mo 24.01.05 18:01
kleine optimierung
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( anfang, ende: integer); var hilfsfeld: TFeld; i,x,y,anfangrechts,endelinks: integer; begin if ende > anfang then begin endelinks := (ende + anfang) div 2; anfangrechts := endelinks + 1; merge_sort(anfang,endelinks); merge_sort(anfangrechts,ende); x := anfang; y := anfangrechts; FOR i := Anfang TO ende DO begin IF sortfeld[x] < sortfeld[y] THEN begin hilfsfeld[i] := sortfeld[x]; sortfeld[x] := 1001; IF x < (endelinks) 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; |
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
|
Verfasst: 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:
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
|
Verfasst: Mo 24.01.05 21:42
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
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
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:
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
|
Verfasst: Mo 24.01.05 22:46
Jetzt müsste der Download gehen.
Der Fehler ist immer noch ein Stack Überlauf.
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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.
_________________ We are, we were and will not be.
|
|
sveno
Beiträge: 40
|
Verfasst: Mo 24.01.05 23:19
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
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
|
Verfasst: 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
|
|
|