Entwickler-Ecke

Grafische Benutzeroberflächen (VCL & FireMonkey) - Quick&Bubblesort spielen verrückt


Mr2Be - Fr 21.11.08 17:36
Titel: Quick&Bubblesort spielen verrückt
Hi,
bin gerade recht verwirrt. habe hier 2 eigentlich funktionierende Algos, also Quicksort und Bubblesort. Die Zahlen an sich sind bei Click sortiert, aber es ergeben sich eigenartige Ergebnisse, so fehlt nach dem Bubblesort Prozess die 1000 gänzlich (durch was sie erstzt wurde weiss ich nicht) während sie nach dem Quicksort Prozess immer doppelt angezeigt wird (ganz am Ende, versteht sich, sortiert^^).
Ein weiteres Mysterium ist, dass sich die Zahlen bei wiederholtem Klicken verändern, da verschwinden dann plötzlich welche oder kommen dazu, keine Ahnung woher er sich die träumt.
Bin für alle Ideen/Erklärungen/Lösungen offen.


Zufallszahlen in 3 arrays und 3 Stringgrids


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
 
var i, n:integer;

begin
   randomize;             
    for i:=1 to 1000 do

      begin

          Zahlen[i] := random (1000)+1;                
          Feld.cells [i-1,0] := InttoStr (i);
          Feld.cells [i-1,1] := Inttostr (Zahlen[i]);    

          Zahlen1[i] := Zahlen[i];    
          Feld1.cells[i-1,0] := inttostr (i);
          Feld1.cells[i-1,1] := inttostr (Zahlen1[i]);   


          Zahlen2[i] := Zahlen[i];    
          Feld2.cells[i-1,0] := inttostr (i);
          Feld2.cells[i-1,1] := inttostr (Zahlen2[i]);   
      end;
end;


Tauschprozedur

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
 
procedure tausche (var a, b : integer);
var cache : integer;

begin
cache:=a;
a:=b;
b:=cache;
end;


Bubblesort

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:
 
var  j, m, Cache, l, TStart, TEnd : integer;



  begin
  TStart:= gettickcount;

  begin
     for m:=1 to 1000 do                                   
     for j:=1 to 1000 do


           if Zahlen1[j]>Zahlen1[j+1]                     
           then

               tausche (Zahlen1[j+1],Zahlen1[j])                
         
  end;            

  TEnd:= gettickcount;
  Time2.caption:=inttostr (TEnd-TStart);
  
  begin

     for l:=1 to 1000 do

       Feld1.cells[l-1,1] := inttostr (Zahlen1[l]);       // Fülle StrGr2 mit neuen, geordneten Werten
  end;

end;


Quicksort

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

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


  repeat

    while Zahlen2[Zl]<Mitte do
      Zl:=Zl+1;

    while Zahlen2[Zr]>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;


Quicksort-Button

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
 
var Zl, Zr, i, TBegin, TEnde :integer;

begin

  TBegin:=gettickcount;


  Zr:=1000;
  Zl:=1;

    quicksort (Zl,Zr);

  TEnde:= gettickcount;
  Time1.caption:= inttostr ( TEnde-TBegin);

  for i:=1 to 1000 do
    begin
      Feld2.cells[i-1,0] := inttostr (i);
      Feld2.cells[i-1,1] := inttostr (Zahlen2[i]);   // fülle StrGr3 mit Zahlen aus Array2
    end;

end;


Dachte besser zu viel als zu wenig.

Greetz Tobi


martin300 - Fr 21.11.08 17:47
lass mal bei den Prozeduren die ganzen var weg
aus

Delphi-Quelltext 
1:
 
procedure tausche (var a, b : integer);

mach

Delphi-Quelltext 
1:
 
procedure tausche ( a, b : integer);


JayEff - Fr 21.11.08 17:47
Spontan fällt mir erstmal auf dass deine Bubblesort nicht korrekt ist.
Bubblesort funktioniert mit einer While-Schleife. Pseudocode:

Quelltext 
1:
2:
3:
4:
5:
 
Solange beim letzten Durchlauf noch eine Vertauschung durchgeführt wurde
   durchlaufe die Elemente
      falls 2 elemente nicht in korrekter reihenfolge sind
         vertausche sie
         vertauschung wurde durchgeführt!


Ausserdem scheinst du willkürlich einzurücken und begins und ends zu verteilen, keine Ahnung wieso die da so im Raum stehen. Deine For-schleifen gehen dagegen immer nur über eine Zeile, da hier der Begin-End block fehlt.

Martin's Ratschlag ist falsch; Es würde zwar keinen Compilerfehler hervorrufen, aber du hast schon recht damit, var-Parameter zu benutzen.


SvenAbeln - Fr 21.11.08 18:11
Keine Ahnung wie groß deine Arrays sind, aber du füllst jeweils die Felder 1-1000 mit Zufallszahlen.
Dein Bubblesort greift dann aber auch auf das Feld 1001 zu.

Delphi-Quelltext 
1:
2:
 
     for j:=1 to 1000 do
           if Zahlen1[j]>Zahlen1[j+1]

Für j=1000 vergleichst du hier mit Zahlen1[1001], das ist aber keine deiner Zufallszahlen.


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!