Sortiermaschine

Narses · Verfasst: So 05.12.04 23:47

Sag mal, nimmst du mich hier auf den Arm? :evil:

Ehemaliges Mitglied Erhaltene Danke: 1

Habe ich nie vorgehabt, sorry. :oops:

Ich verstehe das einfach nicht.

markieren

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 · Verfasst: 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")

Ehemaliges Mitglied Erhaltene Danke: 1

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:

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.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 · Verfasst: 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!

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

Ehemaliges Mitglied Erhaltene Danke: 1

@ 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 · Verfasst: 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.

Ehemaliges Mitglied Erhaltene Danke: 1

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.

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 · Verfasst: 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"

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

Ehemaliges Mitglied Erhaltene Danke: 1

Sorry ich sehe da immer noch nicht durch, könntest du mir das erklären? :oops:

Narses · Verfasst: Di 07.12.04 22:29

Moin!

Kein Thema, nochmal die Aufgabe und der (Pseudo-)Code:

markieren

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 · Verfasst: 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

Ehemaliges Mitglied Erhaltene Danke: 1

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 · Verfasst: Sa 11.12.04 15:32

Moin!

Sowas, war mein Timeout wohl nicht lange genug eingestellt...

OK, was GENAU verstehst du an der letzten Fragestellung nicht? Habt ihr mittlerweile die FOR-Schleife kennengelernt?

cu
Narses

Ehemaliges Mitglied Erhaltene Danke: 1

markieren

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 · Verfasst: 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:

markieren

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:

markieren

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 · Verfasst: 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:

markieren

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:

markieren

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:

markieren

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:

markieren

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 · Verfasst: 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:

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:

const
  Nmax = 4; // Anzahl der Elemente (unser "n")

var
  element: ARRAY[1..Nmax] of <Datentyp>; // könnte z.B. String sein
  hilf: <Datentyp>;                      // dito, aber auf jeden Fall gleicher Typ
  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)); // war "3" = 4-1
    zaehler := zaehler +1;  
  until (zaehler > (Nmax -1)); // war "3" = 4-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:

markieren

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:

markieren

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":

markieren

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); // war "Nmax -1"
    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 · Hält's aus hier Beiträge: 8 WIN XP

@Narses

ich glaube in deinem letzen Quellcodebeispiel hast du einen kleinen fehler gemacht.

markieren

Delphi-Quelltext

1:
2:
3:

:until (index > zaehler); // war "Nmax -1"  
zaehler := zaehler +1;    
until (zaehler <= 0);

da muss glaube ich zaehler:=zaehler-1 hin

Narses · Verfasst: 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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme