Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Sortiermaschine
Delete - Sa 04.12.04 14:32
Titel: Sortiermaschine
Halli Hallo da bin ich wieder.
Wollte mir eine ganz simple Sortiermaschine coden, es hat aber Probleme.
Wenn ich jetzt einige Sachen eintippe z.B. springt er nicht in die nächste Zeile, beim Stringgrid1 // Button1.click
Ich weiss nicht ob er richtig Sortiert, scheint wohl fehler zu geben.
Könnt Ihr mir bitte helfen?
Viele Grüße
Method Man
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:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
| unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, ExtCtrls;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Edit1: TEdit;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Label3: TLabel;
Timer1: TTimer;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
public
end;
var
Form1: TForm1;
x:Integer;
Help1,Help2:String;
y:Integer;
implementation
{$R *.dfm}
procedure TForm1.FormCreate(Sender: TObject);
begin
Randomize;
form1.color:=Random(999999);
Stringgrid1.cells[1,0]:='Vorname';
Stringgrid1.cells[2,0]:='Nachname'; Stringgrid1.cells[3,0]:='Vorname';
Stringgrid1.cells[4,0]:='Nachname';
Stringgrid1.cells[5,0]:='Vorname';
Stringgrid1.cells[6,0]:='Nachname';
Stringgrid1.cells[7,0]:='Vorname';
repeat
x:=x+1;
Stringgrid1.cells[0,x]:=IntToStr(x); Until x=10001;
end;
<span style="font-weight: bold">procedure TForm1.Button1Click(Sender: TObject);
begin
y:=1;
Stringgrid1.Cells[1,y+1]:=Edit1.text;
Stringgrid1.Cells[2,y+1]:=Edit2.text;
y:=y+1; Edit1.text:='';
Edit2.Text:='';
end;</span>
procedure TForm1.Button3Click(Sender: TObject);
begin
x:=0;
repeat x:=x+1;
stringgrid1.cells[1,x]:=IntToStr(Random(100))+IntToStr(Random(100));
stringgrid1.cells[2,x]:=IntToStr(Random(100))+IntToStr(Random(100));
stringgrid1.cells[3,x]:=IntToStr(Random(100))+IntToStr(Random(100));
stringgrid1.cells[4,x]:=IntToStr(Random(100))+IntToStr(Random(100));
stringgrid1.cells[5,x]:=IntToStr(Random(100))+IntToStr(Random(100));
stringgrid1.cells[6,x]:=IntToStr(Random(100))+IntToStr(Random(100));
stringgrid1.cells[7,x]:=IntToStr(Random(100))+IntToStr(Random(100));
Until x=10000;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
y:=1; Repeat If Stringgrid1.cells[1,y]>Stringgrid1.cells[1,y+1]
then
help1:=Stringgrid1.cells[1,y];
Stringgrid1.cells[1,y]:=Stringgrid1.cells[1,y+1];
Stringgrid1.cells[1,y+1]:=help1;
y:=y+1;
Until y=10000;
end;
end. |
Moderiert von 
Tino: Topic aus Sonstiges verschoben am Fr 25.11.2005 um 11:09
Narses - Sa 04.12.04 14:58
Titel: Form
Moin!
Dein Code ist grausam zu lesen. Formatiere das bitte mal neu/sauber und reduziere es auf das notwendige. Was genau ist das Fehlverhalten?
cu
Narses
sourcehunter - Sa 04.12.04 15:46
Warscheinlich hat das StringGrid nicht genug Zeilen. Probier doch einfach ein StringGrid.RowCount:=y+2 bevor du da was reinschreibst.
Delete - Sa 04.12.04 16:35
Doch es hat genug Zeilen, nämlich 10000.
Hier ein Bild davon
Narses - Sa 04.12.04 17:20
Titel: Vorschlag
Moin!
Zunächst mal: nennst du das "vernünfig eingerückter Code"?!? :evil:
Hier meine Version basierend auf dem, was ich aus deinem Code so aufgeschnappt habe.
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:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
| unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, ExtCtrls, ComCtrls;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Edit1: TEdit;
Edit2: TEdit;
ProgressBar1: TProgressBar;
Button4: TButton;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
public
end;
var
Form1: TForm1;
global_break: Boolean;
implementation
{$R *.dfm}
procedure TForm1.FormCreate(Sender: TObject);
var
i: Integer;
begin
Randomize;
StringGrid1.Cells[1,0] := 'Vorname';
StringGrid1.Cells[2,0] := 'Nachname';
StringGrid1.Cells[3,0] := 'Vorname';
StringGrid1.Cells[4,0] := 'Nachname';
StringGrid1.Cells[5,0] := 'Vorname';
StringGrid1.Cells[6,0] := 'Nachname';
StringGrid1.Cells[7,0] := 'Vorname';
for i := 1 to StringGrid1.RowCount-1 do
StringGrid1.Cells[0,i] := IntToStr(i);
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
StringGrid1.Cells[1,StringGrid1.Row] := Edit1.Text;
StringGrid1.Cells[2,StringGrid1.Row] := Edit2.Text;
if (StringGrid1.Row < StringGrid1.RowCount -1) then
StringGrid1.Row := StringGrid1.Row +1;
Edit1.Clear;
Edit2.Clear;
end;
procedure TForm1.Button2Click(Sender: TObject);
var
i,j,
k: Integer;
StrBuf: TStringList;
begin
StrBuf := TStringList.Create;
ProgressBar1.Max := StringGrid1.RowCount;
ProgressBar1.Step := 1;
ProgressBar1.Position := 0;
global_break := FALSE;
Button4.Enabled := TRUE;
for i := StringGrid1.RowCount-2 downto 1 do begin
for j := 1 to i do
if (StringGrid1.Cells[1,j] > StringGrid1.Cells[1,j+1]) then begin
StrBuf.Clear;
for k := 1 to 7 do begin
StrBuf.Add(StringGrid1.Cells[k,j]);
StringGrid1.Cells[k,j] := StringGrid1.Cells[k,j+1];
end;
for k := 1 to 7 do
StringGrid1.Cells[k,j+1] := StrBuf.Strings[k-1];
end;
ProgressBar1.StepIt;
Application.ProcessMessages;
if (global_break) then
exit;
end;
Button4.Enabled := FALSE;
StrBuf.Free;
end;
procedure TForm1.Button3Click(Sender: TObject);
var
i,j: Integer;
begin
for i := 1 to StringGrid1.RowCount-1 do
for j := 1 to 7 do
StringGrid1.Cells[j,i] := IntToStr(Random(100))+IntToStr(Random(100));
end;
procedure TForm1.Button4Click(Sender: TObject);
begin
global_break := TRUE;
ShowMessage('Abbruch des Sortiervorgangs!');
end;
end. |
Du hast min. einen krassen Fehler in deinem Code: dein Dreieckstausch ist nicht mit BEGIN-END gekapselt, deshalb wird von dem IF nur der erste Befehl beachtet. Das dürfte die Sortierfehler hervorrufen.
Dann sollte dir natürlich klar sein, dass du bei den "String-Zahlen" natürlich keine aufsteigende Folge erhalten wirst, sondern eben das Ergebnis eines Textvergleichs...
Wesentliche (strukturelle) Modifikationen an deinem Code von mir: ProgressBar und Abbruch-Button dazugenommen. Beim BubbleSort von 10.000 Zeilen in einem StringGrid war ich dann das Warten leid... :? Ich habe natürlich auch die Anzahl der Zeilen im StringGrid mal auf die Eigenschaft desselben umgestellt, anstatt eine entsprechende Zeilenanzahl anzunehmen...
Ansonsten ist das Verhalten beim Eintragen der Werte aus den Editfeldern so modifiziert, dass die Werte in die aktuelle Cursorzeile geschrieben werden und, wenn möglich, der Cursor eine Zeile tiefer rutscht.
Mir scheint, du programmierst noch nicht sehr lange; deshalb habe ich mal deinen Code "aufgearbeitet". Ich möchte aber anmerken, dass das hier (im Forum) nicht üblich ist!
cu
Narses
Delete - Sa 04.12.04 19:24
@Narses möchte dir sehr danken, dass du dir die Zeit genommen hast und es verbessert hast.
Also ich habe grad in der Schule Delphi als Grundkurs, seit 3-4 Monaten 3 Stunden die Woche und du weisst ja wie langsam es in der Schule geht.
Wie waren grad bei der Variablen Boolean, deshalb ist zwar alles sehr gut was du aufgeschrieben hast, aber so richtig nichts für mich, weil ich nicht viel kapiere.
Es soll so primitiv sein wie es nur geht.
Bei meinem Programm soll er 9999 Mal überprüfen bei 10000 Zahlen bis er es richtig sortiert hat.
Und wenn es geht bei jedem Mal, wenn einer richtig sortiert ist oder schon war nicht noch ein mal von vorne anfangen sondern berücksichtigen.
Danke dir nochmals.
Narses - Sa 04.12.04 20:12
Moin!
@Method_Man: Gerne, kein Problem. Sofern es was nutzt? :wink:
| Zitat: |
in der Schule Delphi als Grundkurs
Bei meinem Programm |
Sag mal, was du da programmierst, ist das für die Schule?
cu
Narses
Delete - Sa 04.12.04 20:45
In der Schule habe ich es richtig programmiert, so dass er sortiert usw.
Am Mittwoch war ich nicht in der Schule und konnte mir den Code deshalb nicht aufschreiben. Ich schreibe am Montag eine Klausur, deshalb habe ich versucht alles wieder zuhause neu zu coden, damit ich es dann in der Klausur auch kann, nur klappt das irgendwie nicht so. :oops:
Wenn ich z.B. einfach nur Buchstaben sortieren möchte, so dass es A,B,C usw. ist, wie müsste ich am leichtesten und primitivsten programmieren?
Narses - Sa 04.12.04 21:45
Titel: Sortieren
Moin!
OK, hört sich erstmal nicht nach "Hausaufgaben" an, ich denke, dann kann ich dir helfen. :wink:
| Method_Man hat folgendes geschrieben: |
| Wenn ich z.B. einfach nur Buchstaben sortieren möchte, so dass es A,B,C usw. ist, wie müsste ich am leichtesten und primitivsten programmieren? |
Es gibt viele Sortier-Algorithmen; das was du in deinem Code aufgegriffen hattest, sah mir auf den ersten Blick nach Bubble-Sort aus, deshalb habe ich in meinem Code auch diesen Algorithmus verwendet. Also, zunächst mal Bubble-Sort.
Es spielt übrigens beim Sortieren keine Rolle, WAS du da sortierst, solange die Elemente alle vom gleichen Typ sind. Deshalb ist es egal, ob es sich um Buchstaben oder Zahlen handelt. Gut, nehmen wir also Buchstaben.
Beispiel-Folge:
D C B A
Die prinzipielle Funktionsweise von BubbleSort könnte man (ganz ganz simpel) folgendermaßen beschreiben:
Wenn "n" die Anzahl der Elemente einer Folge ist, dann mache "n-1"-mal: vergleiche von "links" nach "rechts" nebeneinander liegende Elemente und tausche diese aus, wenn das Linke größer ist, als das Rechte. (Hier steckt noch eine Optimierungsmöglichkeit drin, aber die zeigt sich gleich ganz von alleine)
für unsere Beispiel-Folge:
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:
| 1. Lauf
vorher: D C B A
v-v
C D B A
v-v
C B D A
v-v
nachher: C B A D
2. Lauf
vorher: C B A D
v-v
B C A D
v-v
B A C D
v-v
nachher: B A C D
3. Lauf
vorher: B A C D
v-v
A B C D
v-v
A B C D
v-v
nachher: A B C D |
Die "v"s stellen die Vergleiche dar. Soweit verstanden? Die Redundanz schon entdeckt? (wenn du antwortest und noch Bock hast, können wir auch weiter machen [ähm, und wenn meine Frau mich noch läßt... :wink: ])
cu
Narses
Delete - So 05.12.04 19:56
Ich bräuchte beim Sortierung nur noch Hilfe.
Wenn ich das so eintippe, sortiert er nicht richtig.
Ich will das er mir die Buchstaben richtig sortiert.
Könnte mir jemand behilflich sein?
Ganz simpel bitte.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| procedure TForm1.Button2Click(Sender: TObject);
begin
Repeat If Stringgrid1.cells[1,y]>Stringgrid1.cells[1,y+1]
then
help1:=Stringgrid1.cells[1,y];
Stringgrid1.cells[1,y]:=Stringgrid1.cells[1,y+1];
Stringgrid1.cells[1,y+1]:=help1;
y:=y+1;
Until y=1001;
end; |
Narses - So 05.12.04 20:17
Titel: Angebot
Moin!
Ich versuchte dir mit dem letzten Beitrag zu helfen. Willste dir den nochmal ansehen, dann können wir den Vorgang, wie man (einfach) sortiert, entwickeln.
Oder bist du nur daran interessiert, dass dir jemand deinen Code flickt?
cu
Narses
Delete - So 05.12.04 20:32
@ Narses natürlich würde ich gerne ganz herausfinden wie es funktioniert, aber ich bin erkältet, habe Kopfschmerzen, sonst würde ich es irgendwie schon rausbekommen.
Könntest du mir bitte, wenn es geht mein Code fürs Sortieren flicken, ich meine ganz einfach wie ich angefangen habe, ohne Boolean oder sonstiges.
Danke dir sehr
Gruss Method Man
Narses - So 05.12.04 20:55
Titel: Angebot...
Moin!
| Method_Man hat folgendes geschrieben: |
| natürlich würde ich gerne ganz herausfinden wie es funktioniert |
Dann sollten wir das auch tun! :wink:
| Method_Man hat folgendes geschrieben: |
| aber ich bin erkältet, habe Kopfschmerzen, |
Das ist schade, aber das kann ich auch nicht ändern. :cry:
| Method_Man hat folgendes geschrieben: |
| sonst würde ich es irgendwie schon rausbekommen. |
Dann solltest du das auch versuchen!
| Method_Man hat folgendes geschrieben: |
| Könntest du mir bitte, wenn es geht mein Code fürs Sortieren flicken, ich meine ganz einfach wie ich angefangen habe, ohne Boolean oder sonstiges. |
Hm, ich bin jetzt etwas verwundert. Auf der einen Seite machst du mir nicht den Eindruck, Code abgreifen zu wollen, auf der anderen schon. Das Problem dabei ist, ich habe dir bereits angeboten, den Algorithmus zu entwickeln, was für eine Klausur sicherlich besser ist (wenn man was verstanden hat), als ein Code-Schnipsel "auswendig" zu lernen, den man (möglicherweise) nicht (ganz) verstanden hat.
Das wirklich kuriose ist, ich habe dir in meinem Programm bereits den BubbleSort-Algo codiert, ich habe im Text darunter den Grund für das Fehlverhalten deines Programms erklärt und in dem Code, den du als letzten geschrieben hast, ist der gleiche Fehler wieder drin... :?
Und noch ganz nebenbei: Das ganze (BubbleSort) hat nix mit Booleans zu tun... :wink:
Auf den Punkt: Ich entwickle den Algorithmus gerne mit dir, aber ich werde den Code nicht anfassen (zumal ich das weiter oben bereits getan habe).
cu
Narses
Delete - So 05.12.04 21:16
Hi Narses wie schon gesagt so simpel wie es geht, sollte es sein. Natürlich hast du mir den richtigen Code schon oben geschrieben, den ich in meinem Programm eingebaut habe auch problemlos funzt.
Nur das Problem ist, du hast es zu gut programmiert, wir in der Schule haben ganz primitive Sortiervorgänge gehabt.
Wie z.B." Kopiere das zu help, dann tausch das, danach kopiere zurück usw."
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:
| procedure TForm1.Button2Click(Sender: TObject);
var
i,j,
k: Integer;
StrBuf: TStringList;
begin
StrBuf := TStringList.Create;
ProgressBar1.Max := StringGrid1.RowCount;
ProgressBar1.Step := 1;
ProgressBar1.Position := 0;
global_break := FALSE;
Button4.Enabled := TRUE;
for i := StringGrid1.RowCount-2 downto 1 do begin
for j := 1 to i do
if (StringGrid1.Cells[1,j] > StringGrid1.Cells[1,j+1]) then begin
StrBuf.Clear;
for k := 1 to 7 do begin
StrBuf.Add(StringGrid1.Cells[k,j]);
StringGrid1.Cells[k,j] := StringGrid1.Cells[k,j+1];
end;
for k := 1 to 7 do
StringGrid1.Cells[k,j+1] := StrBuf.Strings[k-1];
end;
ProgressBar1.StepIt;
Application.ProcessMessages;
if (global_break) then
exit;
end;
Button4.Enabled := FALSE;
StrBuf.Free;
end; |
Narses - So 05.12.04 21:23
Tach!
Also, ich will ehrlich sein: Ich glaube, du versuchst dir von mir die Hausaufgaben machen zu lassen. Warum solltest du sonst an Code interessiert sein, der auch als deiner durchgehen soll...
Letztes Angebot: Wir entwickeln den Sortieralgorithmus von Grund auf und du lernst den Code selbst richtig zu schreiben (das können wir gerne jetzt und hier tun, ich hab noch Zeit). Ich versichere dir, es wird "so einfach, wie möglich sein".
Andernfalls mußt du dir jemand anderen suchen, der deine Hausaufgaben macht.
cu
Narses
Delete - So 05.12.04 21:31
@Narses eigentlich hat das nichs mit Hausaufgaben zu tun, weil wir keine Hausaufgaben aufbekommen. :cry:
Aber ich nehme dein Angebot gerne entgegen.
Also soweit ich das verstanden habe:
Wenn Stringgrid1.cells[1,y] größer ist als Stringgrid1.cells[1,y+1]
Dann= wird help1(Variable) zu Stringgrid1.cells[1,y];
Danach= Wird Stringgrid1.cells[1,y] zu Stringgrid1.cells[1,y+1];
Am Ende Wird dann Stringgrid1.cells[1,y] zu help1.
bei jedem Versuch wird die Variable y um 1 erhöht, damit man alle Reihen durch hat, bis
der gewünschte Wert erreicht ist.
Genau an dem Tag wo wir das besprochen haben, war ich ganz wo anders, verliebt im 3. Himmel, also nicht aufgepasst und schon probleme. :lol: :(
Narses - So 05.12.04 21:39
Titel: Bubble-Sort-Entwicklung, die 2.
Moin!
| Zitat: |
| eigentlich hat das nichs mit Hausaufgaben zu tun, weil wir keine Hausaufgaben aufbekommen |
Aha, spannend, wo schreibst du denn deine Klausur?
| Zitat: |
| Aber ich nehme dein Angebot gerne entgegen |
OK, dann möchte ich dich bitten, meine 1. Erklärungsmail nochmal zu lesen und die Frage(n) zu beantworten. Du bist schon mehrere Schritte weiter, so wird das nix.
Es geht mir besonders darum, dass du den dargestellten Ablauf und die als Text "codierte", prinzipielle Funktionsweise genau anschaust.
Nun?
Delete - So 05.12.04 21:48
Wir arbeiten immer zusammen in der Schule, er gibt uns Aufgaben, die wir dann in der Stunde mit seiner Hilfe lösen. Es ist ein Grundkurs mit Anfängern, also mehr kann man da nicht erwarten.
< Bin in der 11. eines Gymnasiums. >
Es ist grad unsere 1. Klausur, von 15 Leuten schreiben nur 4 Leute Klausuren.
Bubble Sort
-1. und 2. vergleichen
----> falsch --> tauschen
-2. und 3. vergleichen
----> falsch --> tauschen
immer weiter bis alles richtig ist.
Narses - So 05.12.04 21:54
OK. Ich nehme mal an, du hast das dargestellte Code-Beispiel verstanden (hoffe ich).
Frage 1: Wie oft wird bei 4 zu sortierenden Buchstaben verglichen und gegebenenfalls getauscht? (wenn man es so macht, wie dargestellt)
Frage 2: Sind in dem Beispiel überflüssige Schritte (Vergleiche) enthalten?
Frage 3: Wenn ja, welche? Wenn nein, warum sind alle Schritte nötig?
Bis gleich :wink:
| Zitat: |
| Es ist ein Grundkurs mit Anfängern, also mehr kann man da nicht erwarten. |
Ich erwarte ja auch nicht mehr. Ist doch OK. Sag bescheid, wenn du hier in der Erklärung nicht mehr mitkommst oder was unklar ist!
| Zitat: |
| Bin in der 11. eines Gymnasiums |
Hatte ich mir schon gedacht, vom Stoff her. :)
Delete - So 05.12.04 22:15
Bei 4 Buchstaben geht er 4 Mal durch, beim 2. Durchlauf braucht er nur 3 Mal durch zu gehen und beim 3. Durchlauf nur 2 Mal, vorrausgesetzt alle 4 Buchstaben stehen falsch.
Und mit Boolean wo man zwei Werte definieren kann: true or false, geht es noch schneller mit dem Sortieren, weil er dann weiss wenn sie richtig stehen, dann nicht mehr sortiert.
Narses - So 05.12.04 22:20
Leider ist deine Antwort nur teilweise richtig. Bitte versuch dich an die Fragestellung zu halten, sonst kann ich dich nicht an die entscheidenden "Erkenntnisse" heranführen. Ich würde mir 3 separate Antworten wünschen.
Bis gleich.
| Zitat: |
| Und mit Boolean wo man zwei Werte definieren kann: true or false, geht es noch schneller mit dem Sortieren, weil er dann weiss wenn sie richtig stehen, dann nicht mehr sortiert |
Das habe ich glaube ich nicht verstanden, aber vielleicht können wir das für den Augenblick beiseite lassen.
Delete - So 05.12.04 22:27
1. Es wird 3 Mal verglichen.
2. Es sind überflüssige vergleiche enthalten.
3. Nach dem Sortieren, weiss man das der als letztes Steht, richtig ist, dann braucht man mit dem nicht mehr zu vergleichen.
Narses - So 05.12.04 22:34
OK, Danke.
Zu 1: Bei mir sind es zwar 9 Vergleiche (je 3 in 3 Läufen), aber ich denke mal, das hast du gemeint :wink:
Zu 2: Klar, war auch nicht schwer zu sehen.
Zu 3: Super! Genau das ist die entscheidende Optimierung!
Welche Schleifen kennt ihr denn schon? Habt ihr die FOR-Schleife schon behandelt?
Wir wollen jetzt einen Peudocode für das Sortieren aufschreiben. Dazu sind zwei Erkenntnisse wichtig:
a) Es gibt zwei Schleifen bei Bubble-Sort.
b) Es ist nicht nötig, alle Elemente mehrfach zu vergleichen.
Frage 4: Wie stehen die beiden Schleifen zueinander? Verschachtelt ( [] ) oder separat () []
Bis gleich
Delete - So 05.12.04 22:40
Hi, wir haben 2 Sorten von Schleifen schon behandelt, nämlich die Post checked Loop Schleife und die While...Do... Schleife.
Bei der Post checked Loop Schleife überprüft er erst am Ende ob der Wert stimmt.
Und bei der While-Do Schleife direkt am Anfang, so wenn es stimmt damit er nicht den Wert noch erhöht und Zeit verliert.
Narses - So 05.12.04 22:41
Gut, macht es zwar etwas "undurchsichtiger" (die FOR-Schleife wäre die 1. Wahl), aber geht auch so.
Aber wie ist es mit Frage 4?
Delete - So 05.12.04 22:42
Leider habe ich die Frage 4 nicht verstanden. :oops:
Narses - So 05.12.04 22:44
Kein Problem.
Sind dir die beiden Feststellungen a) und b) klar?
Delete - So 05.12.04 22:45
ja
Narses - So 05.12.04 22:48
Wo stecken denn in dem Code-Beispiel die beiden Schleifen?
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:
| 1. Lauf
vorher: D C B A
v-v
C D B A
v-v
C B D A
v-v
nachher: C B A D
2. Lauf
vorher: C B A D
v-v
B C A D
v-v
B A C D
v-v
nachher: B A C D
3. Lauf
vorher: B A C D
v-v
A B C D
v-v
A B C D
v-v
nachher: A B C D |
Delete - So 05.12.04 22:58
In jedem Durchlauf hat man garantiert einen Buchstaben richtig gestellt.
1. Lauf
Repeat If D> als C dann tausche, wenn D größer als B dann tausch, dann wenn D größer als A dann tausche, danach ist 100% richtig.
Until x=3;
vorher: D C B A
v-v
C D B A
v-v
C B D A
v-v
nachher: C B A D
Jetzt D ist auf jedem Fall richtig, deshalb muss er nur noch C, B und A vergleichen.
Wenn C > B tausche, wenn C> als A tausche, dann haben wir beide gesichert, dass C und D richtig stehen.
2. Lauf
vorher: C B A D
v-v
B C A D
v-v
B A C D
v-v
nachher: B A C D
Jetzt muss nur noch B und A verglichen werden, B ist > als A deshalb tausche.
3. Lauf
vorher: B A C D
v-v
A B C D
v-v
A B C D
v-v
nachher: A B C D
Die Richtige Stellung.
Narses - So 05.12.04 23:05
OK, du hast, zumindest sprachlich, die beiden Schleifen beschrieben; vielleicht etwas zu genau für den Moment, aber OK.
Hier nochmal die Darstellung, wir ich sie mir vorgestellt hatte:
Quelltext
1:
2:
| ( wiederhole 3 mal
[vergleiche alle elemente und tausche ggfs. aus] ) |
Das würde dem Code-Beispiel entsprechen, wenn man die Optimierung zunächst nicht mit berücksichtigt.
Soweit klar?
Delete - So 05.12.04 23:06
Ja :)
Narses - So 05.12.04 23:12
Antwort zu 4: Die Schleifen sind also verschachtelt! ( [] )
Mal bischen Pseudocode jetzt:
Delphi-Quelltext
1:
2:
3:
4:
5:
| zaehler := 1;
repeat
vergleiche_alle_elemente;
zaehler := zaehler +1;
until (zaehler >= 3); |
Wir wollen mal unterstellen, es handelt sich um unsere Testbuchstaben (4 Stück). Was auch immer "vergleiche_alle_elemente" tut, kommt gleich.
Soweit klar?
Habt ihr schon Arrays behandelt? Strings? Wie habt ihr denn die "Buchstaben" im Unterricht "gespeichert", um sie zu sortieren?
Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.
Delete - So 05.12.04 23:15
Arrays haben wir glaube ich nicht behandelt.
Wir haben uns Variablen namens help1 und help2 ausgedacht und mit String belegt.
Dann haben wir die Buchstaben zum tauschen bei help1 gespeichert, danach wieder eingesetzt.
Bei uns hat er immer den 1. Buchstaben verglichen danach einsortiert.
Beispiel: Vorname Nachname
T> A ----- Torsten Frings
tausche ----- Anton Meier
-----------------------------
Vorname Nachname
Anton Meier
Torsten Frings
Narses - So 05.12.04 23:18
OK, anders gefragt: Wir haben unsere Testbuchstaben "A B C D". Was habt ihr denn im Unterricht zum Sortieren benutzt und wo gespeichert? In dem StringGrid?
Nächste Frage (5): Wie oft wird die Schleife aus dem letzten Beitrag durchlaufen?
Delete - So 05.12.04 23:21
5. Vielleicht 9 Mal
Wir haben den Inhalt von den Stringgrids einfach in eine String Variable gespeichert.
Narses - So 05.12.04 23:24
Meinst du die Antwort 5 ernst?
Delete - So 05.12.04 23:38
Ich meine natürlich 3 Mal, aber 9 wird sie vergleichen.
Narses - So 05.12.04 23:40
Leider falsch, bitte nochmal GENAU hinsehen. Anders gefragt: Wie oft wird "vergleiche_alle_elemente" ausgeführt?
Delete - So 05.12.04 23:46
bis der Zähler größer oder gleich 3 ist?
Narses - So 05.12.04 23:47
Sag mal, nimmst du mich hier auf den Arm? :evil:
Delete - So 05.12.04 23:53
Habe ich nie vorgehabt, sorry. :oops:
Ich verstehe das einfach nicht.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
| procedure TForm1.Button2Click(Sender: TObject);
var help1:String;
begin
y:=1;
Repeat
If Stringgrid1.cells[1,y]>Stringgrid1.cells[1,y+1]
then
help1:=Stringgrid1.cells[1,y];
Stringgrid1.cells[1,y]:=Stringgrid1.cells[1,y+1];
Stringgrid1.cells[1,y+1]:=Stringgrid1.cells[1,y];
y:=y+1;
Until y=Stringgrid1.rowcount;
end; |
Klappt irgendwie nicht.
@ Narses möchte dir danken, dass du dir die Zeit genommen hast mir das mal alles zu erklären, echt sehr nett von dir.
Irgendwie verstehe ich Depp das aber nicht so leicht. :oops:
Narses - So 05.12.04 23:59
OK, hörte sich etwas komisch an, die Antwort.
Also, nochmal, der Pseudocode, wie oft wird dort "vergleiche_alle_elemente" ausgeführt? Nimm dir notfalls ein Blatt Papier und notier dir, welchen Wert "zaehler" hat, dabei gehst du mit dem Stift die Befehle des Pseudocodes durch. Wie oft kommst du dabei an "vergleiche_alle_elemente" vorbei?
Zu deinem Delphi-Code: Können wir das noch einen Moment zurückstellen? Du hast da noch zwei dermaßen fette Fehler drin, dass kann ich nicht einfach korrigieren, wenn du das nicht verstehst. (vielleicht doch noch ein kleiner Hinweis, wenn du´s damit schaffst, soll´s mir halt recht sein: wo sind denn deine beiden Schleifen, von denen wir hier die ganze Zeit reden? Wie funktioniert denn eigentlich ein "IF-THEN")
Delete - Mo 06.12.04 00:16
Vergleiche alle Elemente wird so oft durchgeführt bis alle Buchstaben richtig stehen, denke ich mal.
Jetzt versuche ich es schon seit Stunden, ich schaffe es nicht Buchstaben zu sortieren, was für ein Depp bin ich. :roll:
Eigentlich habe ich in der Schule immer alles schnell kapiert, aber irgendwie kapiere ich jetzt nichts mehr. :roll:
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.Button2Click(Sender: TObject);
begin
x:=1;
y:=1;
Repeat
If Stringgrid1.cells[1,x]>Stringgrid1.cells[1,x+1]
then
help1:=Stringgrid1.cells[1,x];
Stringgrid1.cells[1,x]:=Stringgrid1.cells[1,x+1];
Stringgrid1.cells[1,x+1]:=Stringgrid1.cells[1,x];
x:=x+1;
Until x=Stringgrid1.rowcount;
Repeat
If Stringgrid1.cells[1,y]>Stringgrid1.cells[1,y+1]
then
help1:=Stringgrid1.cells[1,y];
Stringgrid1.cells[1,y]:=Stringgrid1.cells[1,y+1];
Stringgrid1.cells[1,y+1]:=Stringgrid1.cells[1,y];
y:=y+1;
Until y=Stringgrid1.rowcount;
end;
end. |
Sieht es bisschen besser aus?
Kannst du mir irgendein Buch empfehlen mit dem ich Delphi 7 oder generell Delphi gut lernen kann?
Narses - Mo 06.12.04 00:28
Keine Panik! :wink: Wir haben nur ein Problem, ich kann nicht mehr ganz so lange aufbleiben, morgen wieder Maloche... :wink:
| Zitat: |
| Vergleiche alle Elemente wird so oft durchgeführt bis alle Buchstaben richtig stehen, denke ich mal |
Du hängst zu sehr an der fertigen Lösung und dem Wunsch, bereits da angekommen zu sein :wink:
Wie gesagt, spiel mal selbst "Computer" und "führe" die Pseudocode-Zeilen "aus", indem zu mit dem Stift drüber gehst. Dabei notierst du auf einem anderen Zettel, welchen Wert "zaehler" aktuell hat. Und bei dem Ganzen führst du noch eine Strichliste, in der du jedes mal vermerkst, dass du bei "vergleiche_alle_elemente" vorbeigekommen bist. Das hört sich im "Computerzeitalter" vielleicht etwas albern an, aber es hilft! :D
| Zitat: |
| Jetzt versuche ich es schon seit Stunden, ich schaffe es nicht Buchstaben zu sortieren, was für ein Depp bin ich |
Nicht aufgeben! Es ist noch kein Meister aus dem Himmel gefallen. Bis ich Bubble-Sort mal ganz kapiert hatte, sind auch ein "paar Tage" ins Land gegangen... :wink:
Bei deinem neuen Delphi-Code ist leider immer noch ziemlich fett der Wurm drin, das wird heute aber leider nix mehr. Ich kann erst morgen abend wieder ins Forum schauen, weil aus dem LAN auf der Arbeit kann ich mich nicht in im Forum anmelden...
Wie bei Schülern üblich, ist die Zeit mal wieder zu knapp, um das Problem "rechtzeitig" in den Griff zu kriegen. Wenn du noch Lust hast, geht´s morgen abend weiter.
cu
Narses
Delete - Mo 06.12.04 01:02
@ Narses danke für deine Hilfe!
Wir sehen uns dann morgen Abend- ich bin auf jedem Fall da. :)
Gute Nacht und viele Grüße
Narses - Mo 06.12.04 19:10
Titel: Weiter geht´s
Moin!
So, ich habe jetzt erstmal 2 Stunden Zeit. Weiter geht´s :wink:
Hast du "Computer gespielt" und die Antwort herausbekommen? Dabei geht es wohlgemerkt nicht darum, was bei "vergleiche_alle_elemente" passiert, sondern wie oft dieser "Pseudobefehl" ausgeführt wird.
Also, bis gleich
| Zitat: |
| Kannst du mir irgendein Buch empfehlen mit dem ich Delphi 7 oder generell Delphi gut lernen kann? |
Ähm, was du hier gerade versuchst zu lernen, nennt man übrigens Informatik, nicht Delphi. :wink:
Mit den Erkenntnissen aus dieser Informatik kann man dann (unter anderem) auch Delphi-Programme schreiben.
Ich habe nicht so schrecklich viele Bücher über Delphi, zugegeben. Ganz gut finde ich:
"Programmieren lernen in Borland Delphi 7" von Walter Doberenz und Thomas Kowalski aus dem Hanser Verlag. Aber ich habe die Erfahrung gemacht, dass Bücher sehr subjektive Eindrücke hinterlassen und stark vom eigenen Lernverhalten abhängen. Bücher, die ich vielleicht gut finde, mußt du noch lange nicht gut finden und umgekehrt.
Delete - Mo 06.12.04 22:12
Hi Narses ich habe die Klausur heute geschrieben, es ging so, viele der Fragen konnte ich.
Zum Glück hat er nicht gewollt, dass ich das Sortieren in Programmcode aufschreibe, stattdessen sollte ich nur die Funktionsweise erklären, die ich mit deiner Hilfe sehr gut beschreiben konnte. :D
Danke für dein Tipp "Programmieren lernen in Borland Delphi 7" dieses Buch werde ich dann vielleicht anschaffen.
Ich muss leider jetzt für die nächste Klausur lernen, deshalb konnte ich heute nicht, sorry. Morgen bin ich auf jedem Fall dabei.
Danke das du dir die Zeit nimmst.
Viele Grüße
Method Man
Narses - Mo 06.12.04 23:39
Moin!
| Zitat: |
| sollte ich nur die Funktionsweise erklären, die ich mit deiner Hilfe sehr gut beschreiben konnte. |
Na guck mal, hat doch schon was genutzt. Dann kriegen wir auch den Algorithmus noch hin! :wink:
| Zitat: |
| dieses Buch werde ich dann vielleicht anschaffen |
Schau´s dir erstmal (z.B. in der Buchhandlung) an, vielleicht findest du es ja auch nicht so gut!?
| Zitat: |
| deshalb konnte ich heute nicht, sorry. Morgen bin ich auf jedem Fall dabei. |
Das ist hier keine "Pflichtveranstaltung" :D Wir machen das, wenn wir beide Zeit und Lust haben. Lust hab ich noch, Zeit ist schon schwieriger, aber möglich. :?
| Zitat: |
| Danke das du dir die Zeit nimmst |
Nun, ich gehe mal davon aus, dass jemand anders, der diesen Thread nachliest und dabei "zufällig" Bubble-Sort lernt, auch noch was davon hat... :wink:
Also, bis morgen (bin vielleicht so ab 20.30h wieder dabei); du meldest dich - wenn du willst - mit der Antwort auf die letzte Frage zurück.
cu
Narses
Delete - Di 07.12.04 22:19
Sorry ich sehe da immer noch nicht durch, könntest du mir das erklären? :oops:
Narses - Di 07.12.04 22:29
Moin! :wink:
Kein Thema, nochmal die Aufgabe und der (Pseudo-)Code:
Delphi-Quelltext
1:
2:
3:
4:
5:
| zaehler := 1;
repeat
vergleiche_alle_elemente_und_tausche;
zaehler := zahler +1;
until (zaehler >= 3); |
Mir fällt gerade auf, sagt dir "Pseudocode" überhaupt was?
Nochmal die Aufgabe 5: Spiel mal Computer, in dem du mit einem Stift jede Zeile "abhakst", so als ob du (als Computer) den entsprechenden Befehl ausgeführt hättest. Es spielt erstmal keine Rolle, was dieses ominöse "vergleiche_alle_elemente_und_tausche" tut, betrachte es einfach wie einen "normalen" Befehl. Die anderen Anweisungen solltest du schon kennen, daher solltest du damit keine Probleme haben. Während du also "Computer spielst", notierst du dir auf einem Zettel den aktuellen "Inhalt" der Variable "zaehler", sozusagen in deinem RAM :wink: und weiterhin, wie oft du den "Befehl" vergleiche_alle_elemente_und_tausche "ausgeführt" hast (dran vorbeigekommen bist).
Frage soweit klar? Zu schwer?
EDIT(22:10): Wo genau kommst du nicht mehr mit? Kannst du dir nicht vorstellen, wie der Computer den Code oben ausführt? Variablen an sich sind dir ein Begriff (hattest du nicht was von 11. Jahrgang gesagt)?
EDIT: Noch dabei?
Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.
Narses - Do 09.12.04 23:20
Titel: Schade...
Moin!
Schade, es scheint, Method_Man hat aufgegeben.
Nun ist Bubble-Sort ja zwar auch nicht gerade einen Nobel-Preis wert, aber besteht Interesse, den Algorithmus zu Ende zu entwickeln? Möchte jemand für Method_Man einspringen?
Ansonsten würde ich den Thread hier absterben lassen.
cu
Narses
Delete - Sa 11.12.04 00:12
Sorry ich bin noch da, nur sind wir schon längst weiter mit dem Thema. Jetzt programmieren wir Tic Tac To. :lol:
Ich bin an dem Bubble Sort verfahren interessiert, wir können weitermachen.
Ich denke ich habe die Frage nicht ganz verstanden, sonst wüsste ich die Antwort schon.
Narses - Sa 11.12.04 15:32
Moin!
Sowas, war mein Timeout wohl nicht lange genug eingestellt... :D
OK, was GENAU verstehst du an der letzten Fragestellung nicht? Habt ihr mittlerweile die FOR-Schleife kennengelernt?
cu
Narses
Delete - Mo 13.12.04 20:55
Delphi-Quelltext
1:
2:
3:
4:
5:
| zaehler := 1;
repeat
vergleiche_alle_elemente_und_tausche;
zaehler := zahler +1;
until (zaehler >= 3); |
Weiss jetzt nicht was der Pseudocode bedeutet.
Und wie soll ich das mit dem Stift machen?
Was ist: vergleiche alle elemente und tausche?
Ich sehe da nur das der Zähler den Wert 1 bekommt und nach jedem Vergleiche_alle_elemente_und_tausche, der Zähler um 1 erhöht wird, bis er den Wert 3 oder größer erhält.
Method Man
Narses - Mo 13.12.04 22:59
Titel: Verschiedenes
Moin!
| Zitat: |
| Weiss jetzt nicht was der Pseudocode bedeutet. |
Hat mit dem Sortieren (direkt) erstmal nix zu tun, zugegeben. Es geht mir damit auch eher darum, zu sehen, ob du Schleifenkonstruktionen gedanklich zerlegen bzw. die Abbruchbedingung korrekt formulieren/analysieren kannst.
| Zitat: |
| Und wie soll ich das mit dem Stift machen? |
OK, 2 Blatt Papier bereitlegen, auf das eine den Code abschreiben, auf das Andere oben "zaehler := " schreiben, in der Mitte einen dicken Strich malen und als Überschrift der 2. Hälfte "Anzahl vergleiche_alle_elemente_und_tausche" schreiben. Sieht dann ungefähr so aus:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| +--Blatt-1-----------------+ +--Blatt-2----------+
| zaehler := 1; | | zaehler := |
| repeat | | |
| vergleiche_alle_... | | |
| zaehler := zaehler +1; | +-------------------+
| until (zaehler >= 3); | | Anzahl... |
| | | |
+--------------------------+ +-------------------+ |
Jetzt nimmst du einen Stift und tippst in die Zeile auf Blatt 1 vor "zaehler := 1;" und tust so, als wärest du der Computer und würdest den Befehl ausführen. Was tut der Befehl? Der Variablen "zaehler" den Wert "1" zuweisen. Also nimmst du den Stift und schreibst auf Blatt 2 hinter das ":=" eine "1". Befehl ausgeführt. Kannst du mir bis hier hin folgen?
Dann nimmst du wieder den Stift und tippst in die Zeile vor dem "repeat". Was tut der Befehl? Erstmal nix, ist ja nur ein Sprungziel. Also nächster Befehl. In die Zeile vor dem "vergleiche..." tippen. Wir haben gesagt, was auch immer dieser "Befehl" tut, spielt erstmal keine Rolle, wir wollen ja nur wissen, wie oft er denn ausgeführt wird. Deshalb machen wir auf Blatt 2 in der 2. Hälfte einen Strich ("Strichliste"), der andeuten soll, dass dieser Befehl ausgeführt wurde. Deine Blattsammlung sollte etwa so aussehen:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| +--Blatt-1-----------------+ +--Blatt-2----------+
| zaehler := 1; | | zaehler := 1 |
| repeat | | |
| vergleiche_alle_... | | |
| zaehler := zaehler +1; | +-------------------+
| until (zaehler >= 3); | | Anzahl... |
| | | | |
+--------------------------+ +-------------------+ |
Auch dieser Befehl ist damit erstmal ausgeführt (wie gesagt, was auch immer da wirklich passiert). Nächster Befehl. Wir tippen auf Blatt 1 vor die Zeile "zaehler := zaehler +1;". Was tut der Befehl? Auf den Wert der Variablen "zaehler" eins addieren. Wir wenden unseren Blick auf Blatt 2 und "fragen" den Wert der Variablen ab. Was finden wir dort? Genau, eine 1. 1+1=2, also streichen wir die "1" durch und schreiben eine "2" hin. Befehl ausgeführt. Nächster Befehl. Wir tippen wieder auf Blatt 1 vor die Zeile "until (zaehler >= 3);". Was tut der Befehl? Zunächst mal einen Wahrheitswert berechnen. Nämlich: "Ist der Wert der Variablen zaehler >= 3?" Auf den aktuellen Wert (siehe Blatt 2!) bezogen wird also bewertet: "2 >= 3?" Das Ergebnis ist klar: FALSE bzw. unwahr. Wir erinnern uns, was tut "until"? Wenn die Bedingung TRUE bzw. wahr ist, nix, ansonsten wird zur "repeat"-Marke verzweigt. Die Bedingung ist nicht erfüllt, es wird also zu "repeat" verzweigt. Wir tippen also wieder mit unserem Stift in die Zeile vor das "repeat" auf Blatt 1... usw. etc. pp :roll:
Nochmal die Frage: Wie oft wird der Pseudo-Befehl "vergleiche_alle_elemente_und_tausche" ausgeführt? Was auf die obige Art und Weise der "Bearbeitung" bezogen auch bedeuten könnte: Wieviele Striche hast du in die Strichliste im zweiten Teil von Blatt 2 gemalt?
Was genau war jetzt daran so schwer? Ehrlich gesagt, ich hätte von einem Schüler des 11. Jahrgangs so etwas schon als selbstständige Leistung erwartet... :cry:
| Zitat: |
| Was ist: vergleiche alle elemente und tausche? |
Wie ich bereits mehrfach (offensichtlich vergeblich) versuchte zu erklären, sollte das zunächst keine Rolle spielen. Es ist einfach egal, da es in diesem Schritt lediglich um die Schleife geht. Was dieser "Pseudobefehl" tut, wollen wir erst in einem folgenden Schritt klären. OK?
| Zitat: |
| Ich sehe da nur das der Zähler den Wert 1 bekommt und nach jedem Vergleiche_alle_elemente_und_tausche, der Zähler um 1 erhöht wird, bis er den Wert 3 oder größer erhält |
Ja, genau, was etwa der Code in Umgangssprache ist. Aber die entscheidende Frage war, WIE OFT DENN GENAU, sozusagen als ZAHL, wird denn dieser Befehl ausgeführt?!?
| Zitat: |
Hier mein neues Programm- das super funzt.
TIC TAC TO by Method Man |
Schön, dass ihr bereits weiteren Code produziert, ohne den vorangegangenen sauber verstanden zu haben. Allerdings:
Bitte lösche diesen Teil aus deinem Beitrag und erstelle einen neuen Thread, da laut Forumsregeln nur ein Thema pro Thread erlaubt ist und wir hier bereits mehrfach diese Regel "nicht so wirklich beachtet" haben. Deshalb möchte ich auch nicht auf die dazugehörigen Fragen antworten. Wir (die Forumsteilnehmer) können das gerne in einem separaten Thread klären.
OK, zurück zum Thema. Wenn du noch Lust hast, das Sortieren zu entwickeln, solltest du mit der Antwort auf Frage 5 weitermachen.
cu
Narses
Narses - Mi 22.12.04 12:32
Titel: Auflösung - Vielleicht hilft´s ja
Moin!
@Method_Man: scheint, diesmal habe ich es aber geschafft, dich zu vergraulen, was... ? :wink: sorry, war nur gut gemeint.
Also, bevor das zu einer "never-ending-story" wird, soo toll ist Bubble-Sort auch wieder nicht. Ich werde unser angefangenes Algo-Entwickel-Projekt jetzt zu Ende bringen, vielleicht hilft es ja auch, sich das einfach mal anzusehen.
Die so lange ausstehende Antwort auf die Frage 5 ist:
2 mal.
Begründung: "zaehler" hat den Wert "1", wenn die Schleife startet. Da es eine post-checked-loop ist (die Bedingung wird erst am Ende geprüft), wird "zaehler" nach dem ersten Lauf "2" enthalten. Daraus wird nach dem 2. Lauf eine "3", die die Bedingung ">= 3" erfüllt und damit die Schleife beendet.
Das ist aber falsch im Sinne unseres Vorhabens, denn (wie bereits am Anfang in der umgangssprachlichen Formulierung unseres Algorithmus) wir wollen (Anzahl der Elemente -1)mal den Pseudobefehl "vergleiche_alle_elemente_und_tausche" ausführen.
Deshalb muss die korrekte Abbruchbedingung lauten: "
until (zaehler > 3)" (für unser Buchstabenbeispiel, allgemein muss es natürlich mit einer Variablen gelöst werden; dazu später mehr).
Jetzt zu dem mysteriösen Befehl "vergleiche_alle_elemente_und_tausche". Nochmal kurz die umgangssprachliche Aufgabenstellung: Es soll der Reihe nach (von "links" nach "rechts") jedes Element mit seinem "rechten" Nachbarn verglichen werden. Ist der "linke" Nachbar "größer", tausche beide Elemente aus. In Code-Form:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
| index := 1;
repeat
if ( element[index] > element[index +1] ) then
tausche_elemente;
index := index +1;
until (index > 3); |
Auch hier steckt wieder ein Pseudo-Befehl drin: "tausche_elemente". Es ist auf den ersten Blick ganz einfach, zwei Elemente auszutauschen, für den Computer leider nicht. Das Problem nennt man auch
Dreieckstausch, weil der Computer ein Element (was im Prinzip ein "Stück" Speicher ist) nur an eine andere Stelle kopieren kann. Dabei geht aber das vorher dort gespeicherte Element ("Speicherinhalt") verloren (wird überschrieben). Deshalb benötigt man ein weiteres "Stück" Speicher, allerdings nur "kurzfristig", in das man eins der beiden Elemente sichert. Dann kann man das andere Element über das jetzt gesicherte Kopieren und anschließend die Sicherung des ersten Elements über das 2. bügeln. In Code-Form also etwa so:
Delphi-Quelltext
1:
2:
3:
| hilf := element[index];
element[index] := element[index +1];
element[index +1] := hilf; |
Jetzt können wird den Pseudobefehl "tausche_elemente" im vorigen Code-Stück ersetzen, ergibt:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| index := 1;
repeat
if ( element[index] > element[index +1] ) then begin
hilf := element[index];
element[index] := element[index +1];
element[index +1] := hilf;
end;
index := index +1;
until (index > 3); |
Man beachte, dass die Befehle, die als "Ersatz" für den Pseudo-Befehl "tausche_elemente" eingefügt werden, mit einer "begin-end"-Klammer eingefaßt werden müssen, da ALLE Befehle durch die "if"-Anweisung beeinflußt werden müssen, "if" aber nur EINEN Befehl (den nächsten) beachtet.
@Method_Man: hier steckt einer der beiden entscheidenden Fehler in deinem Code!
Damit ist der Pseudo-Befehl "vergleiche_alle_elemente_und_tausche" auch ausformuliert und wir können wieder einen Schritt nach "oben" einsetzen:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| zaehler := 1;
repeat
index := 1;
repeat
if ( element[index] > element[index +1] ) then begin
hilf := element[index];
element[index] := element[index +1];
element[index +1] := hilf;
end;
index := index +1;
until (index > 3);
zaehler := zaehler +1;
until (zaehler > 3); |
Der Code ist zunächst mal (im Prinzip) fertig, wenn man von 4 Elementen ausgeht. :wink:
Wir wollen jetzt noch folgende Dinge unterbringen:
- Die Anzahl der Elemente soll nicht nur "4" betragen, sondern variabel sein -> "n" Elemente,
- Es steckt noch eine Optimierungsmöglichkeit drin, die wir nutzen wollen (weiter oben schon besprochen),
- Abschließend soll natürlich die Anwendung auf ein StringGrid gezeigt werden.
Dazu später mehr.
@Method_Man: vielleicht hast du ja auch Lust, hier wieder einzusteigen?
Narses - Do 30.12.04 14:29
Titel: Auflösung, Teil 2
Moin!
Method_Man hat wohl komplett aufgegeben, schade. Da in dem letzten Post der "linke und rechte Elementnachbar" vertauscht war und deshalb der Algorithmus absteigend sortiert, es aber niemand bemerkt hat, ziehe ich mal folgende Schlüsse daraus: hat keiner gelesen, weil zu simpel oder gelesen und nicht verstanden... ? (Stand jetzt: ist so geändert, dass aufsteigend sortiert wird)
Naja, was man angefangen hat, sollte man auch zuende bringen, also ans Werk.
Die Erweiterung auf "beliebig viele" Elemente setzt etwas mehr Deklaration voraus:
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:
| const
Nmax = 4;
var
element: ARRAY[1..Nmax] of <Datentyp>; hilf: <Datentyp>; zaehler,
index: Integer;
begin
zaehler := 1;
repeat
index := 1;
repeat
if ( element[index] > element[index +1] ) then begin
hilf := element[index];
element[index] := element[index +1];
element[index +1] := hilf;
end;
index := index +1;
until (index > (Nmax -1)); zaehler := zaehler +1;
until (zaehler > (Nmax -1)); end. |
Damit ist der Algorithmus bereits auf eine "beliebige" Anzahl Elemente umgestellt. Jetzt sollen noch die überflüssigen Schritte ausgemerzt werden. Dazu folgende Überlegung:
Nach dem ersten Durchlauf der äußeren Schleife ist das größte Element "ganz hinten" angekommen, praktisch wie eine Luftblase nach oben gestiegen. Daher kommt auch der Name dieses Sortierverfahrens. Die Idee zur Reduktion der unnötigen Schritte ist also leicht aus dieser Erkenntnis abzuleiten: Nach jedem Lauf der äußeren Schleife braucht diese beim nächsten mal nicht mehr bis zum Ende aller Elemente zu laufen, sondern jedes mal ein Element "weniger weit". Der Ablauf mal so dargestellt, in Klammern sind jeweils die Elementnummern angegeben, die verglichen werden:
Quelltext
1:
2:
3:
4:
| (1/2) (2/3) (3/4) -> größtes Element an Position 4 angelangt
(1/2) (2/3) -> 2. größtes an Position 3 angelangt
(1/2) -> 3. größtes an Position 2 angelangt
<fertig> -> kleinstes automatisch an 1. Position übrig |
Hervorgehoben ist jeweils die größte Elementnummer im äußeren Schleifenlauf. Es ergibt sich also die Folge:
3, 2, 1. Bisher hat die Variable "zaehler" aber so "gezählt": 1, 2, 3. Daraus folgt, wir müssen das Verhalten der äußeren Schleife etwas ändern, damit wir deren Laufvariable für die Einsparung der unnötigen Schritte nutzen können:
Delphi-Quelltext
1:
2:
3:
4:
5:
| zaehler := Nmax -1;
repeat
vergleiche_elemente_und_tausche;
zaehler := zaehler -1;
until (zaehler <= 0); |
Tipp am Rande: Es ist zwar möglich die Abbruchbedingung mit "=" statt mit "<=" zu formulieren, aber nicht "weise"... :wink: Wenn man Schleifen mit numerisch signifikanten Abbruchbedingungen formuliert, sollte man immer eine Relation verwenden ("größer" oder "kleiner"), da durch Modifikation der Variablen im inneren des Schleifenkörpers die Abbruchbedingung "verfehlt" werden könnte und daraus eine "Endlosschleife" wird.
Jetzt muss die innere Schleife nur noch bis "zaehler" laufen und nicht mehr bis "Nmax":
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
| zaehler := Nmax -1;
repeat
index := 1;
repeat
if ( element[index] > element[index +1] ) then begin
hilf := element[index];
element[index] := element[index +1];
element[index +1] := hilf;
end;
index := index +1;
until (index > zaehler); zaehler := zaehler -1;
until (zaehler <= 0);
end. |
Damit ist der Algorithmus fertig entwickelt. Die Übertragung auf ein StringGrid sollte nicht mehr wirklich schwer sein, wenn man das Prinzip bis hier hin verstanden hat. Deshalb soll diese Aufgabe der geneigte Leser doch bitte als Übung einfach mal selbst versuchen.
Das Ergebnis kann mit dem Code aus einem meiner frühen Postings in diesem Thread verglichen werden, dort ist eine funktionierende Implementation abgebildet.
cu
Narses
//EDIT: Fehler korrigiert: war zaehler := zaehler +1; und muss natürlich -1 sein! :wink:
Codewriter - So 20.11.05 13:32
@Narses
ich glaube in deinem letzen Quellcodebeispiel hast du einen kleinen fehler gemacht.
Delphi-Quelltext
1:
2:
3:
| :until (index > zaehler); zaehler := zaehler +1;
until (zaehler <= 0); |
da muss glaube ich zaehler:=zaehler
-1 hin
Narses - So 20.11.05 14:59
Moin!
| Codewriter hat folgendes geschrieben: |
| ich glaube in deinem letzen Quellcodebeispiel hast du einen kleinen fehler gemacht. |
Jau, hast recht, hab ich korrigiert; danke für den Hinweis. :wink:
cu
Narses
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 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!