[PHP] Quick-Sort

[Chewie]

Das ist die 1:1-Umsetzung des Quicksort-Algorithmus, wie er auf www.delphi-source.de geschrieben ist. Leider funktioniert er nicht so, wie er es soll. Hat jemand eine Idee?

Code:

function QuickSort(&$array,$lo,$hi) {
  $i = $lo;
  $j = $hi;
  echo "Anfang: i: $i, j: $j
";
  $x = $array[bcdiv($lo + $hi,2,0)];
  while($i<=$j) {
    while($array[$i]<$x) $i++;
    while($array[$y]>$x) $j--;
    if($i <= $j) {
      $h = $array[$i];
      $array[$i] = $array[$j];
      $array[$j] = $h;
      $i++;
      $j--;
    }
  }
  echo "Ende: i: $i, j: $j

";
  if($lo < $j) QuickSort($array,$lo,$j);
  if($i < $hi) QuickSort($array,$i,$hi);
}

Ach ja: Die echos sind nur zur Information da und haben nix mit dem Algorithmus selbst zu tun. Falls der Algorithmus mal funktionieren sollte, kommen die raus. Nur falls es Verwirrungen gibt

[Jan]

Hallo Chewie,
also: Mir fällt zunächst auf, dass du anders als im Tut. von Delphi-Source den zu sortierenden Array nicht als global definiert hast, was ich aber machen würde, ausserdem hast du bei der Variablen-Entgegennahme im Funktionskopf ein "&" vor der array stehen, was nicht notwendig ist, da du ja die bearbeitete Variable jedesmal wieder an die Funktion übergibts -> wegmachen.

Zitat:

Leider funktioniert er nicht so, wie er es soll.

Das ist so das einzige was mir spontan auffällt, wäre nützlich, wenn du noch dabeisagen könntest was nicht so ganz richtig funktioniert.
Ich werd deinen code mal mit globaler variable testen.
Gruß
Jan

[Chewie]

Na ja, ich hab das "&" vor dem Array benutzt, weil ich ja das Array als Referenz übergeben muss. Auf globale Variablen wollte ich eigentlich verzichten. Aber ich muss es mal mit globaler Variable ausprobieren.

Nachtrag: Scheint mit globaler Variable genausowenig zu funktionieren. Ach ja, was nicht funktioniert, ist ganz einfach: Das Array wird nicht richtig sortiert.
Nimm z. B. mal folgendes Array:

Code:

$array[0] = 3;
$array[1] = 1;
$array[2] = 2;
$array[3] = 8;
$array[4] = 4;
$array[5] = 1;

[Jan]

HEHE lol hab deinen Fehler gefunden.. :]

Code:

    while($array[$i]<$x) $i++; 
    while($array[$y]>$x) $j--;

bei der 2. while schleife das soll wohl kaum $y sein oder? schreib da mal $j rein, dann sollte es passen.
Gruß
Jan

[Chewie]

Verdammt
Immer diese dummen Fehler. Warum muss das y auch soviel Ähnlichkeit mit dem j haben ??
Herzlichen Dank, Jan. Ich hab den Code dreimal durchgelesen und trotzdem den Fehler übersehen. Wie schön ist da ein Compiler, der bei jeder undeklarierten Variable meckert...

@ Daniel:
Es wäre ganz schön, wenn du mal einen Kopf-an-die-Wand-Smiley einführen könntest...