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;

//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.


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

user profile iconBergmann89 hat folgendes geschrieben Zum zitierten Posting springen:
selbes Problem...
So geht das aber.

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 - 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.


alzaimar - 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: