Entwickler-Ecke

Grafische Benutzeroberflächen (VCL & FireMonkey) - Quicksort (vllt Rekursion?)


Mr2Be - Di 18.11.08 21:53
Titel: Quicksort (vllt Rekursion?)
n'Abend,
sitzt jetzt schon eine geraume Weile vor meinem Quicksort Algo und komm einfach nicht auf den Fehler...
Das ganze (array mit 100 Zufallszahlen von 1-1000 zur ausgabe im Stringgrid)) ist erst nach mehreren Klicks vollständig sortiert, ist ja irgendwie nicht Sinn der Sache.



Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
 
procedure TForm1.Sortieren2Click(Sender: TObject);

var Zl, Zr, i :integer;

begin


  Zr:=100;
  Zl:=1;

    quicksort (Zl,Zr);


  for i:=1 to 100 do
    begin
      Feld2.cells[i-1,0] := inttostr (i);
      Feld2.cells[i-1,1] := inttostr (Zahlen2[i]);   
    end;

end;



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:
 
procedure quicksort (var Anfang, Ende: Integer);
var  Mitte, Zl, Zr : Integer;
begin

  Zl:=Anfang;
  Zr:=Ende;
  Mitte:=(Anfang+Ende) div 2;


  repeat

    while Zahlen2[Zl]<Zahlen2[Mitte] do


      Zl:=Zl+1;

    while Zahlen2[Zr]>Zahlen2[Mitte] do
      Zr:=Zr-1;

      if Zl<=Zr then
        begin
          tausche (Zahlen2[Zl], Zahlen2[Zr]);
          Zl:=Zl+1;
          Zr:=Zr-1;
        end;

  until Zr<Zl;

    if Anfang<Zr then
      quicksort (Anfang,Zr);

    if Zl<Ende then
      quicksort (Zl, Ende);

end;


vielleicht habt ihr ja ne Ahnung was ich da Falsch gemacht habe...
Danke schonmal,
Tobi.


ub60 - Di 18.11.08 22:59
Dein Ansatz mit der Mitte war falsch. So wie Du das programmierst, kann sich der Wert ändern.
Richtig ist es so:


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
 
  Mitte:=Zahlen2[(Anfang+Ende) div 2];
  repeat
    while Zahlen2[Zl]<Mitte do
      Zl:=Zl+1;
    while Mitte<Zahlen2[Zr] do
      Zr:=Zr-1;

ub60


Mr2Be - Mi 19.11.08 00:01
Titel: Spitze
Danke dir,
hab grad ne Weile gebraucht bis ich das nachvollziehen konnte aber dann fiels mir wie Schuppen von den Augen =)
Hab immer nur darauf geachtet das sich der Zeiger für die Mitte nicht ändert, das sich die Zahlen in dem Array ja verändern :idea: hab ich vollkommen vergessen.
Es läuft :D ,
bis dann
Tobi


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!