Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Problem mit Quicksort
Bergmann89 - Fr 02.01.09 19:58
Titel: Problem mit Quicksort
HI und ein frohes Neues,
ich mach zur Zeit n Englischvortrag über Sortieralgorithmen und ich hab n Problem Quicksort in Delphi umzusetzen.
Ich hab mich streng an den
Pseudocode von Wikipedia [
http://de.wikipedia.org/wiki/Quicksort] gehalten. Und das is bis jetzt dabei raus gekommen:
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:
| TIntArray = Array of Integer; SortedList: TIntArray;
QuickSort(SortedList,0,High(SortedList));
procedure TForm1.QuickSort(var Data: TIntArray; left, right: Integer); var Teiler: Integer; begin if left < right then begin Teiler := Teile(Data, left, right); QuickSort(Data, left, Teiler-1); QuickSort(Data, Teiler+1, right); end; end;
function TForm1.teile(Data: TIntArray; left, right: Integer): Integer; var i, j, Pivot: Integer; begin i := left; j := right; Pivot := Data[right]; repeat while (Data[i] <= Pivot) and (i < right) do inc(i); while (Data[j] >= Pivot) and (j > left) do dec(j);
if i < j then Swap(Data[i],Data[j]);
UpdateList; until i > j;
if Data[i] > Pivot then Swap(Data[i],data[right]);
result := i; end; |
Er springt in die Prozedur rein, arbeitet auch 2-3 mal durch, aber dann is er in ner Endlosschleife drin.
Wär toll wenn jmd das Problem findet...
MfG & Thx Bergmann.
alzaimar - Fr 02.01.09 20:23
Routine 'Teiler'. Pseudocode = 'solange i<j'. Delphi: 'until i>=j'... Du hast geschrieben 'until i>j'...daran könnte es liegen. Ersetze also 'until i>j' mit 'until i>=j'.
Bergmann89 - Sa 03.01.09 03:20
HI,
selbes Problem...
Aber ich glaub trotzdem, dass das ein Fehler bei Wiki is, denn i zählt ja von links (unten) nach rechts (oben) und j zählt von rechts (oben) nach links (unten). Und die Schleife soll erst enden, wenn i an j vorbei ist. Wenn ich die Schleife mit i < j beende, dann wird sie ja nur einmal ausgeführt. Hab ich da jetzt n Denkfehler, oder is das richtig so?!
MfG Bergmann.
jaenicke - Sa 03.01.09 10:33
Bergmann89 hat folgendes geschrieben : |
| selbes Problem... |
So geht das aber.
Und dann funktioniert es auch problemlos bei mir. :nixweiss:
Kann es sein, dass deine Methode Swap fehlerhaft ist? Fehlt vielleicht das var?
// EDIT:
Zu deiner Frage:
Nehmen wir mal das Array [2, 1]. Das Pivotelement wäre 1. j würde durchlaufen bis 0. Also i = j = 0. Deine Schleife würde nie terminieren. Und deshalb muss es >= lauten. ;-)
Bergmann89 - Sa 03.01.09 17:25
HI,
hab was verdreht. mit i >= j gehts. ich dachte alzaimar meint ich soll i > j durch i < j ersetzten und damit gehts dann nich. Naja es war spät xD
Danke für die Hilfe.
MfG Bergmann.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 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!