MINT üben

Insertionsort

Dreißig Übungen zu Insertionsort — vom einzelnen Einfügeschritt bis zur Frage, wann gleiche Werte ihre Reihenfolge behalten.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Dreißig Übungen zum Einfügen, Verschieben und Zählen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.

A1
Aufgaben der Anweisungen
AFB I

Jede Anweisung im Rumpf der Methode insertionSort hat in einer Runde eine feste Aufgabe. Zeichnen Sie in der Tabelle für jede Anweisung genau ein Kreuz in die Spalte ein, die ihre Aufgabe in einer Runde nennt.

Setzen Sie in jeder Zeile das passende Kreuz — hier ist es genau eins pro Zeile. Enter setzt und löscht.
AnweisungmerkenverschiebeneinfügenPosition ändern
int x = a[i];
int j = i - 1;
a[j + 1] = a[j];
j--;
a[j + 1] = x;
x = a[i] merkt das einzufügende Element. a[j + 1] = a[j] verschiebt ein größeres Element nach rechts, a[j + 1] = x fügt x am Ende in die Lücke ein. int j = i − 1 setzt die Position auf das letzte Element des sortierten Teils, j-- verändert sie in jedem Schleifendurchlauf.
Fragen Sie bei jeder Zeile: Wird ein Wert gesichert, kopiert, endgültig gespeichert oder nur ein Index verändert?
Nur die Zeilen mit a[…] auf der linken Seite schreiben in die Reihung — davon kopiert eine ein größeres Element, die andere speichert x.
A2
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.
Ansatz: Erinnern Sie sich an das Applet: Was passiert mit den größeren Karten?
Weiter: Vorsortiert: pro Element ein Vergleich, der sofort falsch ist.
A3
Gleich viele Vergleiche
AFB IIMix

Ein Informatiklehrer behauptet: Bei einer umgekehrt sortierten Reihung braucht Insertionsort genauso viele Vergleiche wie Selectionsort. Leiten Sie das her: Ordnen Sie jeder Zeile die passende Begründung zu. Zwei Karten bleiben übrig.

Ordnen Sie jeder Zeile der Herleitung die passende Begründung zu: Karte anklicken, dann das Feld neben der Zeile (oder Karte direkt auf das Feld ziehen). Mit der Tastatur: Tab zur Karte, Enter, dann Tab zum Feld und Enter. Ein Klick auf ein belegtes Feld legt die Karte zurück. Nicht alle Karten werden gebraucht.

Zu zeigen: Bei einer umgekehrt sortierten Reihung mit n Elementen brauchen Insertionsort und Selectionsort gleich viele Vergleiche.

  1. Vins = 1 + 2 + … + (n − 1)
  2. Vsel = (n − 1) + (n − 2) + … + 1
  3. Vsel = 1 + 2 + … + (n − 1)
  4. Vins = Vsel
Insertionsort summiert 1 + 2 + … + (n − 1), Selectionsort (n − 1) + … + 2 + 1. Rückwärts geschrieben ist das dieselbe Summe, beide ergeben n(n − 1)/2. Die Ablenker sind falsch: Beim Verschieben wird trotzdem verglichen, und Selectionsort sucht das Minimum immer vollständig.
Bestimmen Sie für beide Verfahren getrennt die Summe der Vergleiche je Runde.
Selectionsort zählt rückwärts (n − 1, n − 2, …), Insertionsort vorwärts (1, 2, …) — die Addition ist vertauschbar.