Autor |
Beitrag |
sveno
Beiträge: 40
|
Verfasst: Sa 22.01.05 00:23
Hallo.
Ich habe den bubblesort, shakersort, shellsort, selectionsort und insertionsort inzwischen erfolgreich programmiert und bin nun am quick sort. Aber da krieg ichs nicht hin. kann mir jemand sagen wo mein Fehler liegt?
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 quick_sort(var anfang, ende: integer); var links, rechts, vergleichswert, zaehlerl, zaehlerr, anfangneu, endeneu: integer; begin vergleichswert := (anfang+ende) DIV 2; links := anfang; rechts := ende; zaehlerr := 0; zaehlerl := 0; IF ende > 1 THEN begin WHILE rechts >= links DO begin WHILE sortfeld[links] < sortfeld[vergleichswert] DO begin inc(links); inc(zaehlerl); end; WHILE sortfeld[rechts]> sortfeld[vergleichswert] DO begin dec(rechts); inc(zaehlerr); end; tausche(sortfeld[rechts],sortfeld[links]); inc(links); dec(rechts); end; anfangneu := (links-zaehlerl); endeneu := (rechts+zaehlerr); quick_sort(anfangneu,rechts);
quick_sort(links,endeneu);
end; end; |
Gruss Sven
Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.Moderiert von Christian S.: Topic aus Sonstiges verschoben am Fr 21.01.2005 um 23:29
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Sa 22.01.05 00:40
bin nicht sicher, ob das der einzige Fehler ist, aber die Grenzen für den rekursiven Aufruf sind falsch, soweit ich das jetzt überblicke.
Man muss ja den linken Teil und den rechten Teil der Folge rekursiv sortieren. Also von "anfang" bis "mitte" und von "mitte" bis "ende"
Delphi-Quelltext 1: 2:
| quicksort(rechts, ende); quick_sort(anfang,links); |
Du musst dich jetzt nur noch darum kümmern, dass das Vergleichselement in keiner der beiden Teilfolgen drin ist. Da kommt dann evtl. noch ein +1 oder -1 in die Grenzen rein, aber das kann ich nicht am Quelltext so schnell sehn.
Edit: Nochwas: Die Behandlung des Pivot-Elements dürfte Probleme machen: Man sollte das zuerst noch hinten vertauschen, und vor den beiden rekursiven Aufrufen wieder in die Mitte setzen.
_________________ We are, we were and will not be.
|
|
sveno
Beiträge: 40
|
Verfasst: Sa 22.01.05 11:48
Vielen Dank für deine Hilfe:) Was ist ein Pivot Element?
Ich denke mal das mein Algorhitmus ein völliges Chaos war und deswegen hab ichs gerade nochmal komplett neu versucht:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
| procedure TFrmbubble.BtquickClick(Sender: TObject); var zeit, start: integer; cursor: TCursor; begin cursor := screen.Cursor; Screen.Cursor := crHourGlass; try start := 1; sortfeld := zufallsfeld; starte_zeit(Zeit); quick_sort(start,anzahl); stoppe_zeit(Zeit); anzahl := SpEdAnzahl.Value; kopieresortfeldzustrgrd; lbmsquick.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:
| procedure quick_sort(var anfang, ende: integer); var links, rechts, vergleichswert: integer; begin IF ende > anfang THEN begin links := anfang; rechts := ende; vergleichswert := (anfang + ende) DIV 2; WHILE links < rechts DO begin WHILE sortfeld[links] < sortfeld[vergleichswert] DO inc(links); WHILE sortfeld[rechts] > sortfeld[vergleichswert] DO dec(rechts); tausche(sortfeld[links],sortfeld[rechts]); inc(links); IF rechts > anfang THEN dec(rechts); end;
quick_sort(anfang,rechts);
quick_sort(links,ende);
end; end; |
Dieser läuft nun schon vieeel besser als mein erster, er bricht nicht mehr ab und sortiert. Aber es sind noch vereinzelte wenige Ausreisser da, die nicht dahin gehören wo sie hin sollen. Weiss jemand woran das liegt?
Und ich hab noch eine Frage. In der Procedure TFrmbubble.BtquickClick muss ich zuerst den Start der Zahlenfolge, also 1 in einer Variable speichern damit compiliert werden kann. Warum kann ich das nicht direkt so schreiben: quick_sort(1,anzahl)
Gruss Sven
Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Sa 22.01.05 12:56
Das Pivotelement ist das Element, mit dem verglichen wird. Hab mal meine Info3-Vorlesung genommen, und den dortigen Java-Code in Pascal übersetzt und die Variablen den deinen angepasst. So gehts:
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:
| procedure quick_sort(anfang, ende: integer); var links, rechts, vergleichswert: integer; pivot:integer; begin IF ende > anfang THEN begin vergleichswert := (anfang + ende) DIV 2; tausche(sortfeld[ende],sortfeld[vergleichswert]); pivot:=sortfeld[ende];
links := anfang; rechts := ende-1; repeat WHILE (sortfeld[links] <= pivot) AND (links<ende) DO inc(links); WHILE (sortfeld[rechts] >= pivot) AND (rechts>anfang) DO dec(rechts); if (links < rechts) then tausche(sortfeld[links],sortfeld[rechts]); until (links >= rechts); tausche(sortfeld[links],sortfeld[ende]); quick_sort(anfang,links-1); quick_sort(links+1,ende); end; end; |
_________________ We are, we were and will not be.
|
|
sveno
Beiträge: 40
|
Verfasst: Sa 22.01.05 16:04
So, hab das Programm nach einer anderen Idee neu geschrieben:
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:
| procedure quick_sort(var anfang, ende: integer); var links, rechts, vergleichswert: integer; begin IF ende > anfang THEN begin links := anfang; rechts := ende; vergleichswert := (anfang + ende) DIV 2; WHILE links <= rechts DO begin IF (sortfeld[links] >= sortfeld[vergleichswert]) AND (sortfeld[rechts] <= sortfeld[vergleichswert]) THEN begin tausche(sortfeld[links],sortfeld[rechts]); IF links = vergleichswert THEN vergleichswert := rechts ELSE IF rechts = vergleichswert THEN vergleichswert := links; IF links < ende THEN inc(links); IF rechts > anfang THEN dec(rechts); end ELSE IF sortfeld[links] >= sortfeld[vergleichswert] THEN dec(rechts) ELSE inc(links); end;
quick_sort(anfang,rechts);
quick_sort(links,ende);
end; end; |
Jetzt läufts endlich korrekt
Soo, danke Gausi für deine Hilfe Ich versuch mich jetzt am Merge-Sort
|
|
|