Hallo ihr,

nun, ich hab ein Problem, aber das habt ihr wohl bereits geahnt, wenn ich mich schon hier melde.

Es geht mir darum, ein Struktogramm für Swap-Sort zu entwickeln und grundsätzlich dürfte ich das auch hinbekommen, wenn da nur nicht ... die Zählschleife wäre.

Bei Swap-Sort geht es ja darum, von einer Zahl im Array ausgehend alle Zahlen des Arrays zu zählen, die kleiner sind als sie selbst. Bezeichnen wir es einfach als m. Ist die kleinste Zahl ermittelt, so tauscht man diese mit der Zahl, von der man ausgegangen ist.

Leider schaffe ich genau das nicht.

Beispiel:

5 13 3 2 16 4

Man geht also von der 5 aus und zählt alle Zahlen, die kleiner sind. Dazu braucht man Vergleiche. Man vergleicht also die 5 und die 13 und stellt fest, dass die 13 nicht kleiner ist. Nun wird also die 5 mit der 3 verglichen. Die 3 ist kleiner und somit muss zwischengespeichert werden, dass zumindest eine Zahl existiert, die kleiner ist. (also bis zu diesem Zeitpunkt das m) Nun wird die 5 aber auch mit der 2 verglichen und somit sind bereits zwei Zahlen kleiner als sie selbst. Der Zwischenspeicher muss also dementsprechend angepasst werden, weil m ja nun gleich 2 ist. Bei der 4 erhöht es sich dann nochmal auf 3.

Und dieses Problem kann ich nicht lösen, da ich nicht weiß, welche Schittfolge ich dabei einhalten müsste und wie die Zählschleife zu programmieren ist.

Vielleicht kann mir ja jemand von euch helfen und dafür wäre ich wirklich sehr dankbar!

Liebe Grüße
Phoenixasche

Weißt du allgemein, wie im Struktorgramm Schleifen aussehen?

Vielleicht ist es auch nur ein kleiner Denkfehler. Du musst dir nicht nur die Zahl merken, die niedriger als die ist, mit der du vergleichst, sondern auch die Position im Array. Eigentlich ist die Sortierung und der Algorithmus dann kein Problem. Skizzieren wird hier nur etwas schwierig...

Schau mal bei Wikipedia nach: de.wikipedia.org/wiki/Swap-Sort
Dort sind auch Beispiele angegeben (Das Java-Beispiel kannst du für C# fast 1:1 übernehmen).

Für das Struktogramm brauchst du dann nur zwei Schleifen ineinander verschachteln...

P.S: Bei Swap-Sort brauchst du die Position nicht extra zu speichern, da immer an Position m+1 (bzw. m bei Nullindizierung) geswappt wird...

Hallo ihr zwei,

danke erstmal für eure Antworten. Nur leider war das erhoffte noch nicht dabei.

@freedy

Wie Schleifen im Struktogramm aussehen, weiß ich.

"Vielleicht ist es auch nur ein kleiner Denkfehler. Du musst dir nicht nur die Zahl merken, die niedriger als die ist, mit der du vergleichst, sondern auch die Position im Array. Eigentlich ist die Sortierung und der Algorithmus dann kein Problem. Skizzieren wird hier nur etwas schwierig..."

Hm, aber das muss ich doch nicht wirklich, oder? Ich brauche ja nicht DIE Zahl, die kleiner ist, sondern die Menge der Zahlen, der kleiner sind. Und da ich diese Anzahl dann plus 1 rechne, ist im Grunde auch die Position der kleinsten Zahl zunächst uninteressant. Es geht ja darum, die erste Zahl immer gleich an die richtige Stelle zu tauschen.

@Th69

Auf Wikipedia war ich schon und ich kann mit den Beispielen leider nichts anfangen. Zwar weiß ich, wie Swap-Sort funktioniert, aber die Quelltexte enthalten Befehle, die wir bisher nicht hatten und dementsprechend wenig kann ich damit umgehen.

Aber ich hab mich vorhin hingesetzt und etwas überlegt und etwas auf die Beine gestellt. Ich habe zunächst keinen Fehler gefunden, aber das soll nicht heißen, dass keiner drin ist. Sofern sich das jemand mal anschaut und mir dazu kurz was schreibt, wäre ich natürlich sehr dankbar.


n:=Länge des Arrays;
a:=0;
b:=0;

For i:=1 to n do

Repeat

Repeat
inc(a)
until x(i)>x(i+a);

inc(b);

until x(i+a):=n;

c:=x(i);
x(i):=x(b+1)
x(b+1):=c;
inc(i);
a:=0;
b:=0;

Vielleicht noch kurz zur Erklärung, wie ich mir das Gedacht habe. Man vergleicht also die erste Zahl mit der zweiten und erhöht a (damit also die Indexzahl der zweiten zu vergleichenden Zahl) solange, bis die erste Zahl größer ist als die gerade verglichene. Es existiert also mindestens eine Zahl, die kleiner ist. Das ist b.
Das macht man solange bis die erste Zahl mit allen Ziffern des Arrays verglichen ist. Immer wenn etwas kleineres auftaucht, wird b um eins erhöht.

Ist nun also der erste Durchlauf des Vegleichens abgeschlossen, so tauscht man die erste Zahl mit b+1 und sie steht damit automatisch an der richtigen Stelle und man kann den Index der ersten Zahl erhöhen. Man erhöht also i.
a und b werden wieder auf 0 gesetzt und so wiederholt sich das alles bis i gleich n ist.

Ich weiß nicht, es ginge vermutlich einfacher, aber ist das eine Möglichkeit?

Liebe Grüße

Phoenixasche hat folgendes geschrieben :

Vielleicht noch kurz zur Erklärung, wie ich mir das Gedacht habe. Man vergleicht also die erste Zahl mit der zweiten und erhöht a (damit also die Indexzahl der zweiten zu vergleichenden Zahl) solange, bis die erste Zahl größer ist als die gerade verglichene. Es existiert also mindestens eine Zahl, die kleiner ist. Das ist b. Das macht man solange bis die erste Zahl mit allen Ziffern des Arrays verglichen ist. Immer wenn etwas kleineres auftaucht, wird b um eins erhöht.

Du brauchst doch gar nicht zwei Schleifen, wenn deine erste Schleife abgelaufen ist, was machst du denn dann? Du hast die erste kleinere Zahl gefunden. Aber das ist ja egal, es ist ja ggf. nur die erste von mehreren und du willst ja nur wissen wieviele das sind.

Es reicht also eine Schleife zu nehmen, die bis zum Ende des Arrays läuft und immer wenn die aktuelle Zahl kleiner ist als die betrachtete wird dein Zähler um 1 erhöht.

Phoenixasche hat folgendes geschrieben :

Ist nun also der erste Durchlauf des Vegleichens abgeschlossen, so tauscht man die erste Zahl mit b+1 und sie steht damit automatisch an der richtigen Stelle und man kann den Index der ersten Zahl erhöhen. Man erhöht also i. a und b werden wieder auf 0 gesetzt und so wiederholt sich das alles bis i gleich n ist.

Fast, i darf nur erhöht werden, wenn nur so viele kleinere Zahlen gefunden wurden wie vor der Zahl im Array stehen, denn nur dann gehört die aktuelle Zahl an diese Stelle und man kann einfach die nächste betrachten.

Ich bin mir nicht so sicher, ob du wirklich verstanden hast wie die Sortierung funktioniert, denn deine Beschreibung würde nicht zum Erfolg führen, wenn du i immer erhöhst nach der Vertauschung. Wenn du dir da nicht 100%ig sicher bist, dann nimm lieber Zettel und Stift und probiere es ohne irgendwo dabei nachzuschauen durch. Wenn du es so nicht hinbekommst, dann nimm die Schrittfolge aus Wikipedia zu Hilfe. (Wobei dort die Zählung des Arrays bei 1 beginnt, du musst also i = m vergleichen, nicht i = m + 1!)
Wenn du dann so weit bist, dass du die Sortierung aus dem Kopf auf dem Papier schaffst, dann solltest du es verstanden haben.

Bei Wikipedia sind die Idee und die Implementierung etwas abweichend, weil die Implementierung bereits optimiert ist.

Ich beschreibe es mal ganz kurz mit eigenen Worten, vielleicht hilft das ja:
Ich habe ein Array a, eine Variable index mit dem aktuell betrachteten Index sowie eine Zählvariable m, in der ich die kleineren Zahlen zähle. i ist eine Zählvariable.
Ich beginne mit index = 0 (Arrays sind in Delphi nullbasiert). Ich setze m auf 0 (ich habe ja noch keine kleinere Zahl), dann gehe ich mit i durch das Array beginnend mit index + 1, an jeder Stelle vergleiche ich die Zahl an Position i mit der an Position index und erhöhe m, wenn die Zahl an Position i kleiner ist.
Wenn ich jetzt keine kleinere Zahl gefunden habe, dann erhöhe ich index, denn die aktuelle Zahl steht an der richtigen Stelle.
Wenn ich mindestens eine kleinere Zahl gefunden habe, dann vertausche ich die Zahl an index mit der Zahl an index + m, denn für die Zahl an Position index gibt es index + m kleinere Zahlen. Die, die bereits vor der Zahl stehen (index) + die gefundenen kleineren dahinter (m).
Das ganze nach dem Setzen von index = 0 wiederhole ich bis ich mit index am Ende des Arrays (High(a)) angekommen bin.

Ich habe die Beschreibung nachdem ich sie geschrieben habe in Delphi kopiert und 1:1 umgesetzt, es funktionierte so sofort ohne jede Korrektur .

Danke schön!

Also wie Swapsort funktioniert habe ich ohne Zweifel verstanden. Die Frage ist höchstens, ob ich es in meinem Struktogramm dann auch umsetzen kann.

"Du brauchst doch gar nicht zwei Schleifen, wenn deine erste Schleife abgelaufen ist, was machst du denn dann? Du hast die erste kleinere Zahl gefunden. Aber das ist ja egal, es ist ja ggf. nur die erste von mehreren und du willst ja nur wissen wieviele das sind."

Aber deshalb schaffe ich dich die Zusatzvariable b, oder? Ich gehe ja den ganzen Array durch until x(i+a):=n.

Ich weiß, es wird sicherlich weit einfacher gehen, aber ist es so nicht auch theoretisch möglich? Optimieren kann ich dann immer noch, aber der erste Schritt wäre natürlich ein funktionierender Algorithmus.

"Es reicht also eine Schleife zu nehmen, die bis zum Ende des Arrays läuft und immer wenn die aktuelle Zahl kleiner ist als die betrachtete wird dein Zähler um 1 erhöht."

Im Grunde ist das ja auch mein Ziel, aber ich schaffe es nicht, dass in einer einzigen Schleife umzusetzen, weil ich den Vergleichsvorgang vorm eigentlichen Tauschen trennen möchte und das versuche ich durch diese zwei Schleifen.

"Ich bin mir nicht so sicher, ob du wirklich verstanden hast wie die Sortierung funktioniert, denn deine Beschreibung würde nicht zum Erfolg führen, wenn du i immer erhöhst nach der Vertauschung."

Stimmt. Ich habs grad nochmal durchgerechnet und das funktioniert in der Tat nicht (immer). Ich darf i ja nur erhöhen, wenn i=b+1. Gut, das muss ich noch einbauen.

"(Wobei dort die Zählung des Arrays bei 1 beginnt, du musst also i = m vergleichen, nicht i = m + 1!)"

Aber nach meiner Schleife würde m doch b entsprechen und damit ausschließlich die Anzahl der kleineren Zahlen nach der gerade betrachteten ausdrücken.

Beispiel.

3 6 2 8 7

Er zählt also, dass eine Zahl kleiner ist als die Drei (damit ist b=1) und tauscht x(i) mit b+1.

Er tauscht also die drei an die zweite Stelle und es ergibt sich:

6 3 2 8 7

Nun darf ich i nicht immer erhöhen, sondern lasse erneut b ausrechnen (ist ja eine Schleife) und nur wenn i=b+1 ist, dann erhöhe ich i.

Macht dann also:

2 3 6 8 7

Jetzt geht er durch und stellt fest, nichts ist kleiner als 2. b bleibt also 0 und damit ist i=b+1. i wird erhöht und es wiederholt sich der Vorgang bis zur Acht. Dort stellt er wieder fest, es ist eine Zahl kleiner, b ist also gleich 1.
i, mittlerweile =4, ist also nicht b+i. Somit kommt es zum Tauschvorgang, den ich in meine zweite Schleife gepackt habe.

Zu deiner Beschreibung. Ich muss zugeben, da noch nicht wirklich durchzusehen, einiges aber schon in meinen Schleifen umgesetzt geglaubt zu haben.

Ich weiß nicht, könntest du den Text für Delphi, sofern du ihn noch hast, vielleicht mal hier reinschreiben? Vielleicht verstehe ich ihn dann besser.

Liebe Grüße und danke schön!

Phoenixasche hat folgendes geschrieben :

Ich gehe ja den ganzen Array durch until x(i+a):=n.

An der Stelle stimmt es nicht, denn du musst nicht bis zu einem bestimmten Wert eines Eintrags im Array gehen, sondern durch das ganze Array!

Ich gehe mal nochmal auf deinen am Anfang geposteten Pseudoquelltext (oder soll das Delphi sein? ein Arrayzugriff erfolgt da mit eckigen Klammern x[i]) ein:

Phoenixasche hat folgendes geschrieben :

markieren Quelltext     1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: n:=Länge des Arrays; a:=0; b:=0; For i:=1 to n do     Repeat       Repeat          inc(a)       until x(i)>x(i+a);         inc(b);     until x(i+a):=n;     c:=x(i);     x(i):=x(b+1)     x(b+1):=c;     inc(i);     a:=0;     b:=0;

Du gehst jeden Eintrag durch, aber durch die for-Schleife wird i eben jedesmal erhöht, auch wenn das gar nicht passieren dürfte. Das Thema ist ja erledigt denke ich.

Da du aber das "until x(i+a):=n" danach wieder erwähnt hast will ich dann doch mal genauer erklären was da eigentlich passiert:
Erstens wäre := eine Zuweisung, ein Vergleich wäre =, das mal vorweg.
So, die innere Schleife läuft jetzt bis "x(i)>x(i+a);". Das ist der erste Arrayeintrag, der kleiner ist.
Zwei Probleme:
Erstens, wenn es gar keinen kleineren Eintrag mehr gibt bricht die innere Schleife nicht ab, wenn das Ende des Arrays erreiht ist, es wird auf Einträge dahinter zugegriffen, die es gar nicht gibt. Und wenn die innere Schleife abbrechen würde, würde b erhöht auch wenn es keinen kleineren Eintrag gibt.
Zweitens die Abbruchbedingung "until x(i+a):=n":
Das hieße, dass die Schleife läuft bis der Wert an der zuletzt gefundenen Stelle x(i+a) gleich n, also der Länge des Arrays, ist. Das wird aber kaum je der Fall sein, die Werte im Array haben damit ja gar nichts zu tun. Die Schleife läuft aber nicht bis du den letzten Wert betrachtest.

Beispiel:
1 2
a := 0, b := 0, i := 1

a = 1
x(i) = 1
x(i + a) = x(2) = 2
--> Die Schleife läuft weiter.
a = 2
x(i + a) = x(1 + 2) = x(3) --> nicht definiert

Wie gesagt: Ich habe es genau so geschrieben wie ich es zuletzt geschrieben habe.

Hallo Sebastian,

nun, als ich mich vorher hingestzt und meine Überlegungen in ein Struktogramm gebracht habe, sind mir bereits Probleme aufgefallen. Unter anderem, dass die Bedingung "x(i)>x(i+a)" zur Folge hat, dass die letzte Zahl gar nicht mehr verglichen wird. Alleine könnte ich es aber nicht lösen. Entweder ich hoffe einfach, dass ich den Groteil verstanden habe und die Fehler nicht auffallen, bzw. weniger schlimm behandelt werden oder ich halte mich an deinen Code. Der scheint mir doch recht verständlich zu sein und wenn ich die Variablen etwas dem anpassen, womit ich besser klarkomme, so dürfte ich es wohl auch in ein Struktogramm bringen können.

Mal schauen.

Nochmal danke!