Anfängerproblem mit Quicksort...

[Scipio]

Hallo erstmal,
Ich les hier ja schon länger mit, aber jetzt hab ich auch mal ne Frage:
Ich beschäftige mich gerade mit Bubble- und Quicksort. Bubblesort ist Idiotensicher. Quicksort hingegen bereitet mir einige Schwierigkeiten. Hab jetzt mal den folgenden Code fertig bekommen, der vom Compiler akzeptiert wird und keine Stack-Overflows o.ä. produziert:

Delphi-Quellcode:

procedure TForm1.Quicksort(var S: Array of Integer; US, OS: Integer);
var
M, T, I: Integer;
begin
U := US;
O := OS;
M := S[(U + O) div 2];
  repeat
    while S[U] < M do inc(U);
    while S[O] > M do dec(O);
    if U <= O then
      begin
      T := S[U];
      S[U] := S[O];
      S[O] := T;
      inc(U);
      dec(O);
      end;
  until O < U;
  if O > US then Quicksort(S, US, O);
  if U < OS then Quicksort(S, U, OS);
  Label1.Caption := '';
  for I := US to OS do
  Label1.Caption := Label1.Caption + IntToStr(S[I]) + '; ';
end;

Ich übergebe einen Array, der zu Testzwecken nur 10 Werte enthält, US ist zu Beginn 0, OS ist zu Beginn 10. T ist die Exchange-Variable, I brauche ich nur als Schleifenvariable für das Eintragen der Werte in mein Label.
EDIT:
Habe festgestellt das das var in der Definition(?) der Prozedur fehlte. Hab das jetzt gefixt, und es wirkte Wunder.
Sorry deswegen. Hab aber immernoch ein Problem: Auf magische Art wird einer meiner Werte zu Null. Hat jemand eine Ahnung wo?


Mein Problem ist jetzt, dass es scheint als würde der Code nur einmal ausgeführt, sprich das wird so sortiert, dass es ein Pivot-Element gibt, "rechts daneben", also im oberen Bereich des Arrays gibt es nur größere bzw. gleiche Werte, links nur kleinere. Aber auf den beiden Seiten des Pivotelements herrscht ansonsten Unordnung. Hat jemand ne Ahnung woran das liegen könnte? Habe schon versucht den Code Schritt für Schritt durchzuführen, konnte aber keine Ungereimtheiten feststellen. Der Algorithmus ruft sich mehrmals selber auf, das funktioniert also.
Ich habe mich mit meinem Code grob am Beispiel in Demos\Threads\SortThds.pas orientiert. Ich habe Allerdings versucht den Code zu vereinfachen, da ich die beiden Algorithmen Leuten vorstellen soll, die noch weniger Ahnung als ich haben.
Bin um jede Hilfe dankbar.
Gruß Scipio

[shmia]

Beim Quicksort-Algorithmus können ganz kleine Änderungen wie z.B. kleiner-gleich (<=) statt kleiner (<) teilweise grosse Konsequenzen haben.

Manchmal ist es auch so, dass Quicksort trotzdem noch sortiert dann aber bei bestimmten Eingangsmengen ein sehr ungünstiges Laufzeitverhalten zeigt.

Man muss also sehr vorsichtig sein wenn man an Quicksort etwas "verbessern" will.

Wenn man sich den Pseudocode auf Wikipedia anschaut:

Code:

procedure quicksort(array, left, right)
  if right > left
    select a pivot index (e.g. pivotIndex := (left+right)/2)
    pivotNewIndex := partition(array, left, right, pivotIndex)
    quicksort(array, left, pivotNewIndex - 1)
    quicksort(array, pivotNewIndex + 1, right)

Dann fällt auf, dass hier +1 und und -1 bei den rekursiven Aufrufen verwendet wird.
Das ist bei deinem Code nicht der Fall.

[himitsu]

Zitat:

nur 10 Werte enthält, US ist zu Beginn 0, OS ist zu Beginn 10.

bei 10 Werten hat der letze Wert den Index 9 und nicht 10
(wenn/da das Array einen 0-basierenden Index hat)

[mani64]

Hallo,

also deine Quicksort-Prozedur aus der im Thread #1 angehängten Unit1 kann nicht funktionieren.

Die sieht nämlich so aus

Delphi-Quellcode:

procedure TForm1.Quicksort(S: Array of Integer; US, OS: Integer);
var
M, T, I: Integer;
begin
U := US;
O := OS;
M := (U + O) div 2;

   hier fehlt dann einiges!!

  for I := U to M do
    if S[I] > S[O - I] then
    begin
      T := S[I];
      S[I] := S[O - I];
      S[O - I] := T;
      Inc(U);
      Dec(O)
    end;
  Label1.Caption := '';
  for I := US to OS do
  Label1.Caption := Label1.Caption + IntToStr(S[I]) + '; ';
  if O > US then
    Quicksort(S, US, O);
  if U < OS then
    Quicksort(S, U, OS);
end;

Schick bitte mal die richtige Datei.

Oder schau doch einfach mal hier


LG
mani

[Scipio]

@himitsu: Danke für den Hinweis, war zwar nicht exakt der Fehler, aber in der Gegend hings.


@shmia:
Ich wollte den Code nicht verbessern, sondern verständlicher, und vor allem mit Elementen die dem Rest bekannt sein sollten implementieren. So oder so, dass +/-1 findet sich in der Schleife: inc(U); dec(O);.

@mani:
wtf hab ich da angehängt, das ist so der früheste Anfang aller Überlegungen...

Vielen Dank auf jeden Fall, Gruß Scipio

[Blup]

Die Variable "O" ist nicht lokal deklariert.

[Scipio]

Dafür Global.
Danke trotzdem.
Gruß Scipio

[himitsu]

Zitat von Scipio:

Dafür Global.

Das sollte heißen: Definier sie Lokal, da wo sie hingehört.

Denn sonst überschreiben die rekursiven Aufrufe sich gegenseitig diese Variable.