bubblesortverfahren wiederholen?!?

bernd bubble · Hält's aus hier Beiträge: 9

Hallo,

ich habe bis jetzt ein Program entwickelt, welches zufällige Zahlen von 1-10000 generiert und diese dann nach dem Bubblesortverfahren sortiert.

Ich will jetzt aber das Bubblesortverfahren nicht nur einmal durchlaufen lassen, sondern mehrmals. (im besten Fall soll man die Anzahl der Wiederholungen in ein EditFeld eintragen können)

Das hier ist mein bisheriger Quellcode:

markieren

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:
36:
37:
38:
39:
40:
41:

procedure TForm1.btnBubblesortClick(Sender: TObject);
var
  Zufall : array [0..1001] of Integer;
  x,y : Integer;
  TempInt : Integer;
  Anzahl : Integer;
  time1, time2, DiffTime : TDateTime;
begin

if mmoAnzeige1.Text = ('') then
  begin
    showmessage ('Bitte erstellen Sie zuerst die Zahlen!')
  end
else
    time1 := time;
    Anzahl := mmoAnzeige1.Lines.Count;
    For x := 0 to (1001 - 1) do
      begin
        Zufall[x] := StrToInt(mmoAnzeige1.Lines[x]);
      end;
  For x := 0 to (1001 - 2) do
    begin
      For y := 0 to (1001 - 2) do
        begin
          if Zufall[y] > Zufall[y+1] then
            begin
              TempInt := Zufall[y+1];
              Zufall[y+1] := Zufall[y];
              Zufall[y] := TempInt;
            end;
        end;
    end;

  For x := 0 to (1001 -1) do
    begin
      mmoAnzeige2.Lines.Add(IntToStr(Zufall[x]));
    end;
    time2 := time;
    DiffTime := ( time2 - time1 ) *60 *60 *24;
    lblZeit.caption := Format ( '%2.3f', [DiffTime]  );
end;

Was muss ich denn noch zu diesem Quellcode hinzufügen, dass er das ganze 10 mal durchlaufen lässt? Ich habe es schon mit einer weiteren Variable und einer weiteren FOR Schleife versucht, jedoch zeigt er mir dann eine Fehlermeldung an mit der ich nichts anfangen kann.

Kann mir einer von euch bei meinem Problem helfen?

Dankeschön jetzt schon mal

Mit freundlichen Grüßen

Bernd

Moderiert von Narses: Topic aus VCL (Visual Component Library) verschoben am Mo 05.11.2007 um 14:32

jackle32 · Verfasst: Mo 05.11.07 16:07

Hi,

also erstmal noch ein paar Fragen:
Welche Fehlermeldung kommt den? (Wäre hilfreich zur Ursachenfindung)
Was macht es für einen Sinn Bubblesort mehrfach drüber laufen zu lassen? :gruebel:

So jetzt was vielleicht hilfreiches:

markieren

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:

[...]
else  
    time1 := time;  
    Anzahl := mmoAnzeige1.Lines.Count;  
    For x := 0 to (Anzahl-1) do  
//Wenn du Anzahl ausliest brauchst du auch nur bis dort deine  Werte auslesen, (weiterer Tip: dynamisches Array)
      begin  
        Zufall[x] := StrToInt(mmoAnzeige1.Lines[x]);  
      end;
  
  For x := 0 to (1001 - 2) do  
    begin  
      For y := 0 to (Anzahl-2) do //Begründung siehe oben 
        begin  
          if Zufall[y] > Zufall[y+1] then  
            begin  
              TempInt := Zufall[y+1];  
              Zufall[y+1] := Zufall[y];  
              Zufall[y] := TempInt;  
            end;  
        end;  
    end;  

 
  For x := 0 to (Anzahl -1) do  
    begin  
      mmoAnzeige2.Lines.Add(IntToStr(Zufall[x]));  
    end;  
    time2 := time;  //(Hinweis: wenn du erst hier die Zeit stoppst misst du auch noch die Zeit zum Anzeigen mit)
    DiffTime := ( time2 - time1 ) *60 *60 *24;  
    lblZeit.caption := Format ( '%2.3f', [DiffTime]  );  
end;

Noch eine Kleinigkeit zum Optimieren deines eigentlichen Sortieralgorithmus:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

var 
   Marker: boolean;
[...]


repeat 
   Marker := False;
   For y := 0 to (Anzahl-2) do //Begründung siehe oben 
      begin  
        if Zufall[y] > Zufall[y+1] then  
          begin  
            TempInt := Zufall[y+1];  
            Zufall[y+1] := Zufall[y];  
            Zufall[y] := TempInt;
            Marker := True;  
          end;    
      end;
until Marker;
[...]

Durch diese Änderung erreichst du, dass du nicht immer die maximale Anzahl an Schritten durchlaufen musst, sondern abbrichst wenn die Reihenfolge stimmt.

Gruß Jack

_________________
Es gibt keine dummen Fragen, nur dumme Antworten.

bernd bubble · Hält's aus hier Beiträge: 9

Hallo,

danke schön mal für die Antwort...dadurch ist das Programm viel schneller geworden.
Hier einmal der Teil vom Quellcode und die dazugehörige Fehlermeldung:

markieren

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:

var
  Zufall : array [0..1001] of Integer;
  x,y : Integer;
  TempInt : Integer;
  Anzahl : Integer;
  time1, time2, DiffTime : TDateTime;
  k : Integer;
begin
  k := 0;

if mmoAnzeige1.Text = ('') then
  begin
    showmessage ('Bitte erstellen Sie zuerst die Zahlen!')
  end
else
    time1 := time;
    Anzahl := mmoAnzeige1.Lines.Count;
  For k := 0 to (10) do
  k := k+1;
  For x := 0 to (Anzahl - 1) do
    begin
      Zufall[x] := StrToInt(mmoAnzeige1.Lines[x]);
    end;
.........................

Fehlermdlung:
[Fehler] Unit1.pas(75): E2081 Anweisung für FOR-Schleifenvariablen 'k'
[Fataler Fehler] Project2.dpr(5): F2063 Verwendete Unit 'Unit1.pas' kann nicht compiliert werden

Es stimmt schon... das mit dem wiederholen ist irgendwie sinnlos, aber was man nicht alles für Lehrer so alles macht um gute Noten zu bekommen ;D

Gruß Bernd

jackle32 · Verfasst: Mo 05.11.07 16:38

Okay dann schau mehr mal.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

For k := 0 to 10 do //muss wenn es nur eine Zahl ist nicht in Klammern stehen 
  k := k+1;  
  For x := 0 to (Anzahl - 1) do  
    begin  
      Zufall[x] := StrToInt(mmoAnzeige1.Lines[x]);  
    end;

Das hochzählen der Laufvariablen der Schleife brauchst du nicht zu machen. Die Schleife erhöht ihre Variabel automatisch nach jedem Schleifendurchlauf.

Kann dir jetzt nicht garantieren, das es das ist aber ich könnte mir gut vorstellen, das du so eine Zugriffsverletzung bekommst

Mal noch eine gegen Frage, an welcher Schule lernt man eigentlich Delphi? Bei uns ist die Standard Sprache immer C.

Gruß Jack

_________________
Es gibt keine dummen Fragen, nur dumme Antworten.

bernd bubble · Hält's aus hier Beiträge: 9

Hallo,

ich bin auch nicht gerade begeistert das ich Delphi lerne aber das ist an unserer Schule normal.^^

markieren

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:

procedure TForm1.btnMBubblesortClick(Sender: TObject);
var
  Zufall : array [0..1001] of Integer;
  x,y : Integer;
  TempInt : Integer;
  Anzahl : Integer;
  time1, time2, DiffTime : TDateTime;
  k : Integer;
begin
  <span style="color: orange">k := 0;</span>

if mmoAnzeige1.Text = ('') then
  begin
    showmessage ('Bitte erstellen Sie zuerst die Zahlen!')
  end
else
    <span style="color: orange">For k := 0 to 10 do</span>
    time1 := time;
    Anzahl := mmoAnzeige1.Lines.Count;
    For x := 0 to (Anzahl - 1) do
      begin
        Zufall[x] := StrToInt(mmoAnzeige1.Lines[x]);
      end;
.........................

Meinst du das so oder habe ich das falsch verstanden?
Wenn ich das Program jetzt so starte, dann führt er Bubblesort aber trotzdem nur einmal durch.
Gibt es noch eine "elegantere" Lösung als mit der Variablen?

Gruß Bernd

Jann1k · Verfasst: Mo 05.11.07 16:45

Zitat:

Mal noch eine gegen Frage, an welcher Schule lernt man eigentlich Delphi? Bei uns ist die Standard Sprache immer C.

Mallinckrodt Gymnasium Dortmund, da lernt man das zB.

bernd bubble · Hält's aus hier Beiträge: 9

Sry...es funktioniert ^^

bernd bubble · Hält's aus hier Beiträge: 9

So jetzt noch mal zu meiner anderen Frage:
Ich würde gerne die Anzahl der Wiederholungen in einem EditFeld eingeben und das Program soll den Algorithmus dann so oft wiederholen, wie im Editfeld angegeben.
Hier mal mein Versuch, der jedoch nich funktioniert ^^

markieren

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:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:

procedure TForm1.btnMBubblesortClick(Sender: TObject);
var
  Zufall : array [0..1001] of Integer;
  x,y : Integer;
  TempInt : Integer;
  Anzahl : Integer;
  time1, time2, DiffTime : TDateTime;
  k,h : Integer;
begin
  k := 0;
  h := StrToInt(edtAnzahl.text);

if mmoAnzeige1.Text = ('') then
  begin
    showmessage ('Bitte erstellen Sie zuerst die Zahlen!')
  end
else
    For k := 0 to h do
    time1 := time;
    Anzahl := mmoAnzeige1.Lines.Count;
    For x := 0 to (Anzahl - 1) do
      begin
        Zufall[x] := StrToInt(mmoAnzeige1.Lines[x]);
      end;
  For x := 0 to (Anzahl - 2) do
    begin
      For y := 0 to (Anzahl - 2) do
        begin
          if Zufall[y] > Zufall[y+1] then
            begin
              TempInt := Zufall[y+1];
              Zufall[y+1] := Zufall[y];
              Zufall[y] := TempInt;
            end;
        end;
    end;
    time2 := time;
    DiffTime := ( time2 - time1 ) *60 *60 *24;
    lblZeit.caption := Format ( '%2.10f', [DiffTime]  );

  For x := 0 to (1001 -1) do
    begin
      mmoAnzeige2.Lines.Add(IntToStr(Zufall[x]));
    end;

end;

Hat jemand eine Idee wie das geht?

Gruß Bernd

Jann1k · Verfasst: Mo 05.11.07 16:59

Das Problem ist das deine schleife von 0 bis h kein begin und end hat es wird nur ständig time auf den gleichen wert gesetzt (zeile 1

bernd bubble · Hält's aus hier Beiträge: 9

Und wie ändere ich das um? Einfach indem ich ein begin und ein end setze und das time aus Zeile 19 darüber schreibe?

jackle32 · Verfasst: Mo 05.11.07 17:09

Das grundsatzliche Problem hat Jann1k schon erkannt.

Noch ein paar Anmerkungen:

-Zeile 10: k:= 0 kannst du dir schenken, da du in der For-Schleife immer k auf den Anfangswert setzt

-Wenn du den Sotieralgorithmus genau so oft durchführen willst wie es im Edit steht musst du entweder k bei eins beginnen lassen oder bis h-1 laufen.

-der Ansatz mit der repeat-Schleife hat dir nicht gefallen? Beim Bubblesort ist es sehr oft so. Wenn du die Zeile so oft sortierst wie es Zeichen gibt ist es auf jeden Fall alles sortiert. Meistens ist es aber so, dass nicht ganz links eine Null steht und diese meist nicht ganz nach rechts muss. Daher würde es über die repeat-Schleife nur solange laufen, wie auch wirklch Zahlen ihre Plätze tauschen. (Macht außerdem einen guten Eindruck beim Lehrer, weil du den Algorithmus so schon recht gut optimiert hast).

-Grundsätzliches: bei Schleifen ist es, dass immer das in der Schleife wiederholt wird, was zwischen dem dazugehörigen begin und end steht.
Also:

markieren

Delphi-Quelltext

1:
2:
3:
4:

For k := 0 to h do
begin
  //Hier stehen die zu wiederholenden Anweisungen
end

Fehlen diese "Klammern" (begin end) dann wird immer nur die direkt folgende Zeile wiederholt. In deinem Fall also nur die Zeile:

markieren

Delphi-Quelltext

1:	time1 := time;

und nicht der ganze Algorithmus.

Die Frage die sich jetzt noch stellt ist ob die Schleife an der Stelle wirklich Sinn macht?

Gruß Jack

_________________
Es gibt keine dummen Fragen, nur dumme Antworten.

bernd bubble · Hält's aus hier Beiträge: 9

markieren

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:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:

procedure TForm1.btnMBubblesortClick(Sender: TObject);
var
  Zufall : array [0..1001] of Integer;
  x,y : Integer;
  TempInt : Integer;
  Anzahl : Integer;
  time1, time2, DiffTime : TDateTime;
  k,h : Integer;
  Marker : Boolean;
begin
  h := StrToInt(edtAnzahl.text);

if mmoAnzeige1.Text = ('') then
  begin
    showmessage ('Bitte erstellen Sie zuerst die Zahlen!')
  end
else
    For k := 0 to (h-1) do
    begin
      time1 := time;
      begin
        Anzahl := mmoAnzeige1.Lines.Count;
    For x := 0 to (Anzahl - 1) do
      begin
        Zufall[x] := StrToInt(mmoAnzeige1.Lines[x]);
      end;
repeat
   Marker := False;
   For y := 0 to (Anzahl-2) do
      begin
        if Zufall[y] > Zufall[y+1] then
          begin
            TempInt := Zufall[y+1];
            Zufall[y+1] := Zufall[y];
            Zufall[y] := TempInt;
            Marker := True;
          end;
      end;
until Marker;
    end;
    time2 := time;
    DiffTime := ( time2 - time1 ) *60 *60 *24;
    lblZeit.caption := Format ( '%2.10f', [DiffTime]  );
  For x := 0 to (1001 -1) do
    begin
      mmoAnzeige2.Lines.Add(IntToStr(Zufall[x]));
    end;
    end;
end;

Ich habe immer noch nicht ganz verstanden wie ich das umsetzen muss ^^
Könnt ihr mir anhand des Quellcodes vielleicht zeigen was ihr meint (die Repeat-Schleife habe ich jetzt auch eingefügt

)

Gruß Bernd

[Edit: Sry war am Anfang der falsche Quellcode!!!]

bernd bubble · Hält's aus hier Beiträge: 9

@ Jack: Was würdest du denn anstelle einer Schleife einfügen?

jackle32 · Verfasst: Mo 05.11.07 17:41

markieren

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:
36:
37:
38:
39:

else
  time1 := time;
  Anzahl := mmoAnzeige1.Lines.Count;

  For k := 0 to (h-1) do
  begin
    
    For x := 0 to (Anzahl - 1) do
    begin
      Zufall[x] := StrToInt(mmoAnzeige1.Lines[x]);
    end;

    repeat
      Marker := False;
      For y := 0 to (Anzahl-2) do //Begründung siehe oben
      begin
        if Zufall[y] > Zufall[y+1] then
        begin
          TempInt := Zufall[y+1];
          Zufall[y+1] := Zufall[y];
          Zufall[y] := TempInt;
          Marker := True;
        end;
      end;
    until Marker;
  end

  time2 := time;
  DiffTime := ( time2 - time1 ) *60 *60 *24/h;
  lblZeit.caption := Format ( '%2.10f', [DiffTime]  );

  For x := 0 to (1001 -1) do
    begin
      mmoAnzeige2.Lines.Add(IntToStr(Zufall[x]));
    end;

end;
 
end.

Also ich hätte es jetzt so gemacht, die farbigen begin end gehören zu der farbigen Schleife. Jetzt holst du dir vor dem Sortieren die Zeit, dann sortierst du so oft wie du eingibst und dann wird die Zeit gestoppt. Dadurch bekommst du eine genauere Zeit, wie lange du zum sortieren brauchst, da sich die Fehler auf mehrere durchläufe verteilen. Wenn du die Zeit durch h teilst bekommst du natürlich wie lange einmal sortieren gedauert hat, natürlich kannst du das auch weg lassen und hast dann eben die Gesamtzeit.

Noch was grundsätzliches: Versuche die Schleife auch immer mit einrücken darzustellen. Hilft sehr beim lesen und dann auch beim Fehler suche und finden. Was auch noch hilft sind Absätze nach Sachen die Zusammengehören. Hab mal versucht das oben einigermaßen zu zeigen. Hoffe dir fällt auf, das es so leichter zu lesen ist.

Gruß Jack

_________________
Es gibt keine dummen Fragen, nur dumme Antworten.

zongo-joe · Beiträge: 134 win xp prof D3, D4, D7

@jackle32
sry, wenn ich mich da einmische, aber wo ich das grad so sehe:
muss das in der Repeat-Schleife nicht heissen

until not marker ?

schliesslich soll das prog ja aufhören, wenn nix mehr getauscht wird
oder steh ich da aufm Schlauch ?

Gruß
Zongo

bernd bubble · Hält's aus hier Beiträge: 9

genau dazu habe ich auch noch mal eine frage...
Mir wird nicht ganz klar was Marker ist. Müsste da nicht stehen until marker = ????
Bis zu welchem "Wert" wiederholt er denn die Schleife?

Gruß Bernd

jackle32 · Verfasst: Di 06.11.07 14:13

@[quote] zongo-joe: Ja danke hast du recht, war ein Fehler von mir, muss natürlich heißen

markieren

Delphi-Quelltext

1:	until not Marker

Zur Erklärung:

Die repeat-Schleife durchlauft alles was zwischen repeat und until steht solange die Anweisung hinter until nicht "true" wird. Als Anweisung ist dabei ein Vergleich ( mit =,>,< usw.), ein mit mit weiteren Operatoren Verknüpfter Vergleich ( also irgenwas mit and oder or) oder eben eine Variable vom Typ boolean, gültig.
Ist ja auch logisch, da ein Vergleich entweder stimmt oder nicht stimmt, dabei wird im Programm für wahre Vergleiche immer der Wert "true" zurückgegben oder im anderen Fall eben "false". D.h. egal ob Variable von Typ boolean oder Vergleich für das Programm ist das Ergebniss das gleiche.

Jetzt zu deinem Programm.

Marker ist hier nur ein Variable vom Typ boolean, die auch jeden anderen Namen haben könnte. Ich hab sie Marker genannt, da ich gerne Variablen verwende, aus deren Namen man auf die Funktion und der Inhalt schließen kann. Also Marker weil der sich was merkt (könnte man auch Merker nennen).

Hier ist es jetzt so, dass immer wenn das Programm in die repeat-Scleife rein läuft der Wert von Marker auf "false" gesetzt wird. Diesen Wert behält diese Variable auch, bis das Programm in die if-Anweisung läuft und das macht es ja wenn was getauscht werden muss. Jetzt ist der Wert von Marker "true" und beim until Spring das Programm wieder nach oben wo repeat steht.
Hat man jetzt den Fall, alle Zahlen sind schon an der richtigen Stelle (was sehr oft der Fall ist, auch wenn noch die maximal nötige Anzahl an Durchläufen durchlaufen wurde), dann wird ja nichts mehr getauscht, d.h. der Wert der Marker Variablen ist bis es zu until geht auf "false". Jetzt wird mit dem dem NOT aus "false" "true" und der Ausdruck nach until insgesamt also "true". Jetzt wird die Schleife abgebrochen und die Auswertung gestartet.
Der Vorteil dieses Aufbaus ist, das du immer die Schleif abbrichst wenn alle Zahlen an der richtigen Stelle sind, egal wann das ist. D.h. mal sortierst du 100 mal bis alles stimmt, mal vielleicht aber auch nur 50 mal. Du brauchst dir drüber aber keine Gedanken während der Laufzeit zu machen, da dies ja diese repeat until Schleife für die Erledigt.

Was jetzt ziemlich lang, aber ich hoffe es hat dir geholfen

Gruß Jack

Ergänzung:

Alternativer Aufbau der repeat-Schleife ohne NOT im until

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

repeat  
      Marker := True;  
      For y := 0 to (Anzahl-2) do //Begründung siehe oben  
      begin  
        if Zufall[y] > Zufall[y+1] then  
        begin  
          TempInt := Zufall[y+1];  
          Zufall[y+1] := Zufall[y];  
          Zufall[y] := TempInt;  
          Marker := False;  
        end;  
      end;  
    until Marker;

_________________
Es gibt keine dummen Fragen, nur dumme Antworten.

jackle32 · Verfasst: Di 13.11.07 18:05

Und hats jetzt funktioniert?

Gruß Jack

_________________
Es gibt keine dummen Fragen, nur dumme Antworten.

Logikmensch · Beiträge: 390 Win XP Delphi 2007 Prof., XE2, XE5

Also bitte eines am Rande:

Man sollte sich immer mit den Grundlagen beschäftigen, bevor man daran geht, ein Problem zu lösen. Ich kann auch nicht mit dem Auto losfahren, bevor ich den Zündschlüssel umgedreht habe. ;-)

(d.h. ich kann schon, wenn mich einer abschleppt, aber Fahren lerne ich dadurch nicht).

In dem geposteten Code fehl(t)en zu viele Begins und ends, als dass es Sinn machte, sich die Problematik (das Sortieren) überhaupt vorzunehmen.
Auch hier ist - ich wiederhole mich gerne - der Fleiß VOR den Erfolg gesetzt. :mahn:

_________________
Es gibt keine Probleme - nur Lösungen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme