Startliste im Schwimmverein
AFB I–IIEin Schwimmverein speichert die 50-m-Zeiten (in Sekunden) von sechs Schwimmerinnen in der Reihung zeiten. Für die Startliste sollen die Zeiten aufsteigend sortiert werden; dazu wird die Grundversion von Bubblesort verwendet.
- Beschreiben Sie das Vorgehen von Bubblesort in einem Durchlauf und nennen Sie, was nach dem k-ten Durchlauf über die Reihung feststeht.
- Stellen Sie die Belegung von
zeitennach jedem der fünf Durchläufe in einer Tabelle dar und notieren Sie jeweils die Anzahl der Vertauschungen. - Leiten Sie eine Formel für die Anzahl der Vergleiche der Grundversion bei n Elementen her und geben Sie den Wert für diese Reihung an.
- Erläutern Sie am Ergebnis aus b), wie eine Variante mit einer booleschen Variable
getauschtArbeit einsparen kann, und geben Sie an, wie viele Vergleiche sie hier benötigt.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
In einem Durchlauf werden von links nach rechts benachbarte Elemente zeiten[j] und zeiten[j+1] verglichen; ist das linke größer, werden beide über eine Hilfsvariable getauscht. Das größte Element des unsortierten Teils wird dadurch bis an dessen rechtes Ende mitgenommen. Nach dem k-ten Durchlauf stehen die k größten Werte in ihrer endgültigen Reihenfolge am rechten Ende; der unsortierte Teil umfasst noch die Indizes 0 bis n − 1 − k.
Erwartungshorizont zu Aufgabe b)
| Durchlauf | zeiten danach | Vertauschungen |
|---|---|---|
| 1 | 24 31 22 27 35 38 | 4 |
| 2 | 24 22 27 31 35 38 | 2 |
| 3 | 22 24 27 31 35 38 | 1 |
| 4 | 22 24 27 31 35 38 | 0 |
| 5 | 22 24 27 31 35 38 | 0 |
Insgesamt 7 Vertauschungen.
Erwartungshorizont zu Aufgabe c)
\(V=(n-1)+(n-2)+\dots+1\). Die Summe zweimal (vorwärts und rückwärts) untereinander geschrieben ergibt \(n-1\) Spalten mit jeweils dem Wert \(n\): \(2V=n(n-1)\), also \(V=\frac{n(n-1)}{2}\). Für \(n=6\): \(V=\frac{6\cdot5}{2}=15\) Vergleiche (5 + 4 + 3 + 2 + 1).
Erwartungshorizont zu Aufgabe d)
Nach Durchlauf 3 ist die Reihung bereits sortiert; die Durchläufe 4 und 5 ändern nichts mehr. Die Variante setzt vor jedem Durchlauf getauscht auf falsch und bei jedem Tausch auf wahr. Gab es in einem Durchlauf keinen Tausch, ist die Reihung sortiert und die äußere Schleife endet. Erst Durchlauf 4 zeigt, dass nichts mehr getauscht wird — er muss also noch ausgeführt werden. Eingespart wird nur Durchlauf 5: \(5+4+3+2=14\) statt 15 Vergleiche.
Beliebte Podcast-Folgen
AFB II–IIIEin Podcast-Portal zeigt seine Folgen nach der Zahl der Abrufe geordnet an. Die Abrufzahlen (in Hundert) stehen in der Reihung abrufe. Das Entwicklungsteam verwendet dafür den folgenden Algorithmus.
- Analysieren Sie den Algorithmus: Geben Sie an, in welcher Reihenfolge er sortiert, und erklären Sie die Aufgabe der Variablen
getauscht. - Wenden Sie den Algorithmus auf
abrufe = {42, 39, 26, 18, 51}an. Geben Sie die Belegung nach jedem Durchlauf der äußeren Schleife sowie die Gesamtzahl der Vergleiche an. - Implementieren Sie den Algorithmus als Methode
sortiere, die eineint-Reihung als Parameter erhält. - Das Team behauptet: „Jeden Tag kommt nur eine neue Folge hinzu; sie wird am Ende der bereits sortierten Reihung angehängt. Die Reihung ist also fast sortiert, und dank
getauschtist unser Verfahren dann immer schnell.“ Beurteilen Sie diese Aussage.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
&&.Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Getauscht wird, wenn das linke Element kleiner ist als das rechte: Kleine Werte wandern nach rechts, der Algorithmus sortiert absteigend (Bubblesort). getauscht merkt sich, ob im aktuellen Durchlauf mindestens ein Tausch stattfand. Ist es nach einem Durchlauf noch falsch, ist die Reihung sortiert und die äußere Schleife endet vorzeitig. Mit dem Startwert wahr wird der erste Durchlauf sicher ausgeführt.
Erwartungshorizont zu Aufgabe b)
| Durchlauf | abrufe danach | Vergleiche | Tausch |
|---|---|---|---|
| 1 | 42 39 26 51 18 | 4 | 1 |
| 2 | 42 39 51 26 18 | 3 | 1 |
| 3 | 42 51 39 26 18 | 2 | 1 |
| 4 | 51 42 39 26 18 | 1 | 1 |
Nach Durchlauf 4 ist i = 4 und die Schleife endet über die erste Bedingung. Insgesamt 4 + 3 + 2 + 1 = 10 Vergleiche — trotz der fast sortierten Eingabe nicht weniger als in der Grundversion.
Erwartungshorizont zu Aufgabe c)
public static void sortiere(int[] abrufe) {
boolean getauscht = true;
int i = 0;
while (i < abrufe.length - 1 && getauscht) {
getauscht = false;
for (int j = 0; j < abrufe.length - 1 - i; j++) {
if (abrufe[j] < abrufe[j + 1]) {
int hilf = abrufe[j];
abrufe[j] = abrufe[j + 1];
abrufe[j + 1] = hilf;
getauscht = true;
}
}
i++;
}
}Gleichwertig ist eine for-Schleife mit der Bedingung i < abrufe.length - 1 && getauscht.
Erwartungshorizont zu Aufgabe d)
Die Aussage stimmt nur teilweise. Hat die neue Folge die wenigsten Abrufe, ist die Reihung schon sortiert: ein Durchlauf ohne Tausch, \(n-1\) Vergleiche — schnell. Hat sie dagegen die meisten Abrufe, muss sie von ganz hinten nach ganz vorn. Bubblesort bewegt sie pro Durchlauf aber nur um einen Platz nach vorn; jeder Durchlauf enthält einen Tausch, ein Abbruch findet nicht statt. Es werden alle \(n-1\) Durchläufe mit \(\frac{n(n-1)}{2}\) Vergleichen ausgeführt (wie in b). „Immer schnell“ ist also falsch: Im ungünstigen Fall wächst der Aufwand quadratisch mit n. Sinnvoller wäre, die neue Folge wie bei Insertionsort von hinten an ihren Platz einzufügen — höchstens \(n-1\) Vergleiche. Vollständig ist die Antwort, wenn beide Fälle unterschieden und der ungünstige Fall mit der Bewegung „ein Platz pro Durchlauf“ begründet wird.