Dreißig Übungen zu Insertionsort — vom einzelnen Einfügeschritt bis zur Frage, wann gleiche Werte ihre Reihenfolge behalten.
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
Stimmt's? — Fünferserie
AFB I
Nennen Sie zu jeder Aussage über Insertionsort, ob sie stimmt.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5
Insertionsort passt sich den Daten an: Zwischen \(n-1\) (vorsortiert) und \(\frac{n(n-1)}{2}\) Vergleichen (umgekehrt sortiert) ist alles möglich.
Überlegen Sie, was in jeder Runde mit den größeren Elementen geschieht: Werden sie getauscht oder nur kopiert?
Vorsortiert: pro Element ein Vergleich, der sofort falsch ist.
A2
Die Reihung vor dem Einfügen
AFB I
Der Pegelschreiber eines Flusses speichert fünf Wasserstände in cm: pegel = {4, 9, 15, 22, 11}. Die Elemente mit Index 0 bis 3 sind sortiert, Insertionsort beginnt die Runde i = 4 mit dem Zwischenspeicher x = 11. Bestimmen Sie, welche Zeichnung die Reihung zeigt, nachdem die while-Schleife beendet ist, aber bevor x geschrieben wird.
Klicken Sie die passende Zeichnung an und prüfen Sie dann. Mit der Tastatur: Tab zur Karte, Enter auswählen.
Die Elemente 22 und 15 sind größer als 11 und werden einen Platz nach rechts kopiert. Bei 9 endet die Schleife (9 > 11 ist falsch). Weil nur kopiert wird, steht 15 noch an Index 2 — dieser Platz wird gleich von x überschrieben. Zeichnung A (4, 9, 15, 15, 22) zeigt genau diesen Zustand; in B ist 15 nicht verschoben, in C ist auch 9 gerückt, und in D ist x schon geschrieben.
Gehen Sie von rechts nach links: Welche Elemente sind größer als 11 und werden deshalb kopiert?
Kopiert wird nur nach rechts, nichts wird gelöscht. Die Schleife stoppt vor 9, und x wird erst danach geschrieben — an Index 2 steht noch der alte Wert.
A3
Vergleiche auf der Skala
AFB II
Ein Sportverein lässt seine Mitgliederlisten verschiedener Länge von Insertionsort ordnen und zählt dabei die Vergleiche von Reihungselementen. Ermitteln Sie für jede Karte die Zahl der Vergleiche und ziehen Sie die Karte an die passende Stelle der Skala. Ein Teil der Karten ist vorsortiert, ein Teil umgekehrt sortiert.
Ziehen Sie jede Karte am Griff ⠿ an die passende Stelle der Skala — die Marke zeigt Ihnen beim Ziehen, wo sie einrastet. Ohne Ziehen: Karte antippen, dann auf die Skala tippen. Tastatur: Enter nimmt die Karte, ←/→ (oder ↑/↓) verschiebt (mit Shift in großen Schritten), Enter setzt.
Vorsortiert sind es n − 1 Vergleiche (6, 8), umgekehrt sortiert n(n − 1)/2: für n = 3 sind das 3, für n = 5 sind es 10, für n = 6 sind es 15 und für n = 7 sind es 21 Vergleiche.
Unterscheiden Sie zuerst: Bei einer vorsortierten Reihung kostet jedes Element genau einen Vergleich, bei einer umgekehrt sortierten wandert Element i über alle i Vorgänger.
Vorsortiert: n − 1. Umgekehrt: 1 + 2 + … + (n − 1) = n(n − 1)/2. Setzen Sie die Werte von n ein.
