Autor Beitrag
Bergmann89
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: 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:

ausblenden volle Höhe 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;

//Aufruf: 
QuickSort(SortedList,0,High(SortedList));

//Quicksort Prozeur:
procedure TForm1.QuickSort(var Data: TIntArray; left, right: Integer);
var Teiler: Integer;
begin
  if left < right then                      //wenn left kleiner right dann
    begin
      Teiler := Teile(Data, left, right);   //suche teiler
      QuickSort(Data,     left, Teiler-1);  //bearbeite die geteile Liste weiter
      QuickSort(Data, Teiler+1,    right);
    end;
end;

//Teiler-Funktion:
function TForm1.teile(Data: TIntArray; left, right: Integer): Integer;
var i, j, Pivot: Integer;
begin
  i := left;
  j := right;
  Pivot := Data[right];
  repeat
    //Element suchen was größer als das Pivot-Element ist
    while (Data[i] <= Pivot) and (i < right) do
      inc(i);
    //Element suchen was kleiner als das Pivot-Element ist
    while (Data[j] >= Pivot) and (j > left) do
      dec(j);

    //wenn nicht aneinander vorbei gelaufen, dann Tauche die Elemente
    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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19339
Erhaltene Danke: 1752

W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Sa 03.01.09 10:33 
user profile iconBergmann89 hat folgendes geschrieben Zum zitierten Posting springen:
selbes Problem...
So geht das aber.
ausblenden Delphi-Quelltext
1:
  until i >= j;					
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
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)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Sa 03.01.09 19:17 
user profile iconBergmann89 hat folgendes geschrieben Zum zitierten Posting springen:
hab was verdreht. mit i >= j gehts. ich dachte alzaimar meint ich soll i > j durch i < j ersetzten.

user profile iconalzaimar hat folgendes geschrieben Zum zitierten Posting springen:
Ersetze also 'until i>j' mit 'until i>=j'.
Wer lesen kann, ist klar im Vorteil. Oder wer ausgeschlafen ist. :wink:

_________________
Na denn, dann. Bis dann, denn.