Dreißig Übungen zu Bubblesort, Durchläufen und vorzeitigem Abbruch — von AFB I bis AFB III.
Ihr Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen in gemischter Reihenfolge — Sie klicken, ziehen, ordnen, rechnen und knobeln. Jede Übung gibt Ihnen sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fahren Sie über ein unterstrichenes Arbeitswort, sehen Sie, was es genau von Ihnen verlangt.
A1
Der Weg durch einen Durchlauf
AFB I
Die innere Schleife von Bubblesort wiederholt immer dieselben Schritte. Zeichnen Sie den Weg eines Durchlaufs: Schalten Sie jedes Feld mit „?“ so weiter, dass der Ablauf stimmt.
Schalten Sie jedes Feld mit „?“ per Klick weiter, bis der Ablauf stimmt — die Pfeile laufen im Uhrzeigersinn. Mit der Tastatur: Tab zum Feld, Enter oder ↓ weiter, ↑ zurück.
j < a.length − 1 − i prüfenwahrDurchlauf
Zuerst wird die Schleifenbedingung geprüft. Ist sie wahr, werden die Nachbarn a[j] und a[j + 1] verglichen; steht das größere Element links, werden beide über die Hilfsvariable getauscht. Danach wird j um 1 erhöht und die Bedingung erneut geprüft. Erst wenn sie falsch ist, endet der Durchlauf.
Der Durchlauf beginnt mit der Prüfung der Schleifenbedingung. Welche zwei Elemente stehen danach zur Entscheidung?
Getauscht wird nur, wenn das linke Element größer ist, und zwar über hilf. Zum Schluss rückt j weiter, nicht i.
A2
Wer arbeitet wie?
AFB IIMix
Selectionsort, 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.
A3
Stimmt's? — Fünferserie
AFB I
Nennen 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.
Aussage 1 von 5
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.
