Sortieralgorithmus - Aufgabe mit Lösungsidee

[Susi123]

Ich habe folgendes Struktogramm vorliegen und bin mir nicht sicher, wie ich es auf das Array anwenden soll, bzw. ob ich es richtig verstanden habe.





In der ersten Zeile soll ich eine Schleife machen, die von n (hier: 6) bis 2 läuft mit der Zählervariable i
in der zweiten Zeile soll ich eine Schleife machen, die von 2 bis i (hier: 6) läuft mit der Zählervariable j
Die dritte Zeile ist eine if-Abfrage. Die Bedingung von dieser Abfrage ist A[j-1] >= A[j].

Ich beginne damit: A [1] >= A [2] --> Bedingung ist erfüllt, da Z >=A. Das heißt ich tausche A[1] mit A[2], also sieht das Array jetzt folgendermaßen aus: W Z O E L F.
Dann prüfe ich: A[2] >= A [3] --> Bedingung ist erfüllt, da Z >=O. Das heißt ich tausche A[2] mit A[3], also sieht das Array jetzt folgendermaßen aus: W O Z E L F.
Das ganze führe ich bis zum Schluss durch und komme dann auf: W O E L F Z.

Habe ich den Algorithmus damit richtig angewandt oder ist da ein Denkfehler enthalen? Irgendwie bin ich mir da so unsicher.

---
Wie muss ich den Algorithmus ändern, dass er stabil arbeitet? Stabil bedeutet doch , dass die Reihenfolge der Datensätze gleichbleibt, deren Sortierschlüssel auch gleich sind. Also wenn zwei Mal das gleiche Element vorkommt, dass dann die ursprüngliche Reihenfolge beibehalten wird.

 

[LimDul]

Ich habe folgendes Struktogramm vorliegen und bin mir nicht sicher, wie ich es auf das Array anwenden soll, bzw. ob ich es richtig verstanden habe.

Anhang anzeigen 12702

Anhang anzeigen 12701

In der ersten Zeile soll ich eine Schleife machen, die von n (hier: 6) bis 2 läuft mit der Zählervariable i
in der zweiten Zeile soll ich eine Schleife machen, die von 2 bis i (hier: 6) läuft mit der Zählervariable j
Die dritte Zeile ist eine if-Abfrage. Die Bedingung von dieser Abfrage ist A[j-1] >= A[j].

Ich beginne damit: A [1] >= A [2] --> Bedingung ist erfüllt, da Z >=A. Das heißt ich tausche A[1] mit A[2], also sieht das Array jetzt folgendermaßen aus: W Z O E L F.
Dann prüfe ich: A[2] >= A [3] --> Bedingung ist erfüllt, da Z >=O. Das heißt ich tausche A[2] mit A[3], also sieht das Array jetzt folgendermaßen aus: W O Z E L F.

Das ganze führe ich bis zum Schluss durch und komme dann auf: W O E L F Z.

Habe ich den Algorithmus damit richtig angewandt oder ist da ein Denkfehler enthalen? Irgendwie bin ich mir da so unsicher.

Wie viele Schritte hast du durchgeführt? Du hast glaub du hast nur den Fall für i=n gemacht, aber die äußere Schleife läuft ja auch noch.

Also vergleiche: 1 mit 2, 2 mit 3, 3 mit 4, 4 mit 5, 5 mit 6 und dann vergleiche 1 mit 2, 2 mit 3, 3 mit 4, 4 mit 5 usw.

 

[mihe7]

Wie muss ich den Algorithmus ändern, dass er stabil arbeitet?

Überleg mal, was (und warum) passiert, wenn zwei gleiche Buchstaben aufeinander folgen...

 

[Susi123]

Ich habe wohl die äußere Schleife nicht bedacht und nur 4 Vergleiche gemacht


Ich beginne damit: A [1] >= A [2] --> Bedingung ist erfüllt, da Z >=A. Das heißt ich tausche A[1] mit A[2], also sieht das Array jetzt folgendermaßen aus: W Z O E L F.
Dann prüfe ich: A[2] >= A [3] --> Bedingung ist erfüllt, da Z >=O. Das heißt ich tausche A[2] mit A[3], also sieht das Array jetzt folgendermaßen aus: W O Z E L F.
Das ganze führe ich bis zum Schluss durch und komme dann auf: W O E L F Z.

Danach geht es dann weiter A [1] mit A [2] verglichen...
A [2] mit A [3] verglichen.
A [3] mit A [4] verglichen.
A [4] mit A [5] verglichen.
A [5 mit A [6] verglichen.

Dann wieder von vorne...
weitere 5 Vergleiche (Sorry für die komplizierte schrittweise Darstellung)
Dann sieht das so aus
ZWOELF

WZOELF
WOZELF
WOEZLF
WOELZF
WOELFZ

OWELFZ
OEWLFZ
OELWFZ
OELFWZ
OELFWZ

EOLFWZ
ELOFWZ
ELFOWZ
ELFOWZ
ELFOWZ

ELFOWZ
EFLOWZ
EFLOWZ
EFLOWZ
EFLOWZ

EFLOWZ
EFLOWZ
EFLOWZ
EFLOWZ
EFLOWZ

Damit habe ich dann bei 6 Elementen insgesamt 5 * 5 Vergleiche. Stimmt die Berechnung?

Überleg mal, was (und warum) passiert, wenn zwei gleiche Buchstaben aufeinander folgen...
Dann würde die beiden Buchstaben vertauscht werden, was eigentlich nicht passieren darf, wenn der Algorithmus stabil sein soll. Aber wie ändere ich das, sodass der Sortieralgorithmus stabil bleibt.

 

[kneitzel]

Nein, schau noch einmal genau auf die innere Schleife. Bis wohin läuft diese?
Also wie viele Durchgänge hat der erste Durchlauf?
Wie viele Durchgänge hat der zweite Durchlauf?#
u.s.w.

 

[Susi123]

Ahhh...ich check es nicht.
Die äußere Schleife läuft von n bis 2. Also hier von 6 bis 2. Das heißt: 6, 5, 4, 3, 2 --> Das sind 5 Elemente
Die innere Schleife läuft von 2 bis n. Also hier von 2 bis 6. Das heißt: 2, 3, 4, 5, 6 --> Das sind 5 Elemente.
Aber da muss wohl irgendwo ein Denkfehler sein.

 

[kneitzel]

Die innere Schleife läuft von 2 bis n.

Ja, schau noch einmal genau nach, was da steht. Die innere Schleife läuft nicht bis n.

 

[Susi123]

Von 2 bis i. Aber was ist i? Ich dachte i = n?
Die Struktogramm überfordert mich völlig. Hab bisher noch nie so etwas gesehen und soll jetzt das erste Mal eins verstehen und anwenden.

 

[kneitzel]

Nein, i ist doch die Zählvariable der äußeren Schleife und ändert sich damit von Durchlauf zu Durchlauf.

 

[Susi123]

Danke für die Rückmeldung und die Bemühungen. Leider komme ich damit nicht weiter. Was bedeutet das in der Umsetzung? Was muss ich mit womit vergleichen und in welcher Reihenfolge? Ich weiß nicht mal was Schleife und Zählvariable wirklich bedeuten.

 

[kneitzel]

Dann betrachten wir nur die äußere Schleife: "for i := n down to 2"

Dies bedeutet, dass wir eine Schleife haben, es soll also etwas mehrfach wiederholt werden. Und zwar soll dabei i (die Zählvariable, also die Variable, in der man zählt) von n runter bis auf 2 gezählt werden.
Also erst ist i = n. Beim nächsten Durchgang ist i = n-1, dann n-2 u.s.w. bis i=2 ist. Dann hört die Schleife auf.

 

[Susi123]

Also im konkreten Beispiel ist zuerst i = 6, dann 5, 4, 3, 2. Danach hört die Schleife auf.
So weit bin ich dabei...

 

[mihe7]

Und für jedes i führst Du jetzt die innere Schleife aus, die ja nur bis i zählt.

i=6
  j=2
  j=3
  j=4
  j=5
  j=6 (=i)

i=5
  j=2
  j=3
  j=4
  j=5 (=i)

i=4
  j=2
  j=3
  j=4 (=i)

usw.

 

[Susi123]

Ah danke... jetzt bin ich wieder dabei 🙂

Ich vergleiche also
i = 6, Elemente 1-2, 2-3, 3-4, 4-5, 5-6
i = 5, Elemente 1-2, 2-3, 3-4, 4-5
i = 4, Elemente 1-2, 2-3, 3-4
i = 3, Elemente 1-2, 2-3
i = 2, Elemente 1-2

Also habe ich bei 6 Elementen 15 Vergleiche.

 

[mihe7]

Das sieht mir vernünftig aus.

 

[Susi123]

Vielen herzlichen Dank für deine konstruktive Hilfe.

Hat noch jemand eine Idee, wie man allgemein beschreiben kann, wie viele Vergleiche notwendig sind und was geändert werden muss, damit der Algorithmus stabil arbeitet?

 

[kneitzel]

Was für Gedanken hast Du Dir denn dazu gemacht? Bezüglich dem letzten Punkt ist ja schon die Problematik in der Aufgabe beschrieben worden.... Evtl. spielst Du den Algorithmus selbst ein paar Mal auf einem Zettel durch....

 

[mihe7]

was geändert werden muss, damit der Algorithmus stabil arbeitet?

Dann würde die beiden Buchstaben vertauscht werden, was eigentlich nicht passieren darf, wenn der Algorithmus stabil sein soll. Aber wie ändere ich das, sodass der Sortieralgorithmus stabil bleibt.

Du hast doch die Lösung schon fast hingeschrieben 🙂 Welche Stelle im Algorithmus sorgt denn dafür, dass es zu einem Vertauschen gleicher Buchstaben kommt?

 

[Susi123]

Das "größer gleich" führt dazu, dass auch gleiche Elemente vertauscht werden. Also sollte man das "gleich" weglassen und der Algorithmus würde dann stabil arbeiten?

Bei 6 Elementen bin ich auf 15 Vergleiche gekommen. 5+4+3+2+1 = 15
Bei 5 Elementen komme ich auf 4+3+2+1 = 10 Vergleiche.
Bei 4 Elementen komme ich dann auf 3+2+1= 6 Vergleiche.
Bei 7 Elementen 6+5+4+3+2+1 = 21 Vergleiche.

Kann man das dann allgemein damit beschreiben?

 

[mihe7]

Das "größer gleich" führt dazu, dass auch gleiche Elemente vertauscht werden. Also sollte man das "gleich" weglassen und der Algorithmus würde dann stabil arbeiten?

Probier's aus 🙂 Auf Papier, dann kannst Du den Buchstaben einen Index geben, also z. B. BE1E2RE3

Kann man das dann allgemein damit beschreiben?

Nein, so kann man das nicht schreiben. Eine Summe von n=1 bis n-1 (also bis 0) über n wäre 0. Du bräuchtest eine Summe von i=1 bis n-1 über i. Das Ergebnis ist der kleine Gauss: (n-1)*n/2 = (n² - n)/2.

Beispiel: (7² - 7)/2 = 42/2 = 21

Normalerweise interessiert aber nicht die genaue Anzahl der Vergleiche, sondern eine Größenordnung, d. h. die Zeitkomplexität des Algorithmus. Für diese wird die O-Notation verwendet: Die Zahl der Vergleiche liegt in O(n²), wächst also nicht wesentlich schneller als n². Der Algorithmus hat somit eine quadratische Laufzeit.

 

[Susi123]

Dankeschön.