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