| Autor |
Beitrag |
Bergmann89
      
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: Fr 02.01.09 19:58
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 gehalten. Und das is bis jetzt dabei raus gekommen:
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.
_________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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'.
_________________ Na denn, dann. Bis dann, denn.
|
|
Bergmann89 
      
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: 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.
_________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
|
|
jaenicke
      
Beiträge: 19339
Erhaltene Danke: 1752
W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Sa 03.01.09 10:33
Bergmann89 hat folgendes geschrieben : | | selbes Problem... |
So geht das aber. Delphi-Quelltext Und dann funktioniert es auch problemlos bei mir.
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 
      
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: 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.
_________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Sa 03.01.09 19:17
_________________ Na denn, dann. Bis dann, denn.
|
|
|