Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen zu Bubblesort — vom einzelnen Durchlauf über Code und Zählen bis zu Varianten. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Stimmt's? — Fünferserie
AFB INennen Sie zu jeder Aussage über Bubblesort (aufsteigend sortieren), ob sie stimmt.
Fünf Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Bubblesort bringt große Werte schnell nach rechts, kleine Werte aber nur langsam nach links. Die Grundversion arbeitet immer gleich viel: \(\frac{n(n-1)}{2}\) Vergleiche.
Ansatz: Denken Sie an das Bild der Blase: Welches Element wird bei jedem Tausch mitgenommen?
Weiter: Die Grundversion hat zwei feste Zählschleifen — ihre Durchlaufzahl hängt nicht von den Werten ab.
A2
Ein Durchlauf in der Tracetabelle
AFB IEin Kiosk speichert die Verkaufszahlen einer Woche in verkauf = {6, 11, 2, 9, 4}. Stellen Sie den ersten Durchlauf von Bubblesort als Tracetabelle dar: Belegung der Reihung nach dem Vergleich von verkauf[j] und verkauf[j + 1].
Füllen Sie alle Felder aus und prüfen Sie dann. Die Zeile j = 0 ist vorgegeben. In die letzte Spalte gehört „ja“ oder „nein“.
| j | [0] | [1] | [2] | [3] | [4] | Tausch? |
|---|---|---|---|---|---|---|
| 0 | 6 | 11 | 2 | 9 | 4 | nein |
| 1 | ||||||
| 2 | ||||||
| 3 |
Die 11 wird ab j = 1 bei jedem Vergleich mitgenommen und landet am Ende:
6 2 9 4 11. Die 2 ist dagegen nur einen Platz nach links gerutscht — für sie braucht es noch weitere Durchläufe.Ansatz: Vergleichen Sie in jeder Zeile nur das Paar an den Indizes j und j + 1 — mit dem Stand aus der Zeile darüber.
Weiter: Bei j = 1 steht 11 vor 2: Tausch. Danach „reist“ die 11 weiter nach rechts.
A3
Wer arbeitet wie?
AFB IIMixSelectionsort, Insertionsort und Bubblesort sortieren dieselbe Reihung auf unterschiedliche Weise. Ordnen Sie jede Beschreibung dem Verfahren zu, auf das sie zutrifft.
Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken Sie dann die Ziffer des Korbs (0 legt sie zurück).
1Selectionsort
2Insertionsort
3Bubblesort
Selectionsort holt in jeder Runde das Minimum nach vorn, Insertionsort steckt ein Element in den sortierten Teil und verschiebt dabei, Bubblesort tauscht nur Nachbarn und bringt das Maximum nach rechts. Nur bei Bubblesort kommen kleine Werte pro Durchlauf höchstens einen Platz voran.
Überlegen Sie bei jeder Beschreibung, ob ein Minimum gesucht, ein Element eingefügt oder ein Nachbarpaar getauscht wird.
Nur Bubblesort arbeitet ausschließlich mit benachbarten Paaren. Der Zwischenspeicher x gehört zum Einfügen, das Minimum zum Auswählen.