Übungsaufgaben
Zehn Ü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.
Nennen Sie zu jeder Aussage über Insertionsort, ob sie stimmt.
Ein Bastler sortiert Kabellängen (in cm). Nach drei Runden gilt laenge = {12, 27, 35, 51, 30, 8, 44}; die ersten vier Elemente sind sortiert. Wenden Sie die nächste Runde von Insertionsort an.
Zwischenspeicher x in dieser Runde:
Vergleiche in dieser Runde:
Verschiebungen in dieser Runde:
Die Reihung danach:
Verschiebungen in der Runde danach (x = 8):
27 > 30 ist falsch und beendet die Schleife — er zählt trotzdem mit: 3 Vergleiche. In der nächsten Runde ist 8 kleiner als alle fünf sortierten Elemente: 5 Verschiebungen, 5 Vergleiche, danach ist j = -1.Ordnen Sie jede Eigenschaft dem Sortierverfahren zu, auf das sie zutrifft.
Ein Lieferdienst sortiert Lieferzeiten in Minuten: zeit = {38, 14, 52, 9, 27}. Stellen Sie den Ablauf von Insertionsort in der Tracetabelle dar.
1 2 3 4 5. Enter prüft ebenfalls.| i | x | Verschiebungen | Vergleiche | zeit danach |
|---|---|---|---|---|
| 1 | 14 | |||
| 2 | 52 | |||
| 3 | 9 | |||
| 4 | 27 |
i = 1 und i = 3 wandert x bis ganz nach vorn — dann endet die Schleife über j >= 0, ohne dass ein weiterer Vergleich von Elementen stattfindet. Deshalb ist dort die Zahl der Vergleiche gleich der Zahl der Verschiebungen.i = 3: x = 9 ist kleiner als 52, 38 und 14 — drei Verschiebungen, drei Vergleiche.Tom hat Insertionsort programmiert, aber seine Methode liefert falsche Ergebnisse. Analysieren Sie den Code Zeile für Zeile und korrigieren Sie die fehlerhaften Zeilen.
j = i würde x zuerst mit sich selbst verglichen. a[j] < x verschiebt die kleineren Elemente — das sortiert absteigend und zerstört den sortierten Teil. a[j] = a[j + 1] kopiert in die falsche Richtung: Das größere Element soll nach rechts rücken.a = {4, 2} durch: Welchen Wert hat j beim ersten Vergleich?i - 1, Bedingung a[j] > x, Kopie von links nach rechts.Die Reihung r = {5, 11, 16, 23, 13} ist bis Index 3 sortiert. Beschreiben Sie Schritt für Schritt, wie die Java-Methode der Inhaltsseite das Element 13 einfügt.
j auf das Ende des sortierten Teils setzen.a[j + 1] ← a[j], dann j ← j − 1.Eine Reihung hat \(n=12\) Elemente. Berechnen Sie die Anzahl der Vergleiche und Verschiebungen im besten und im ungünstigsten Fall.
- Insertionsort, vorsortiert: Vergleiche
- Insertionsort, vorsortiert: Verschiebungen
- Insertionsort, umgekehrt sortiert: Vergleiche
- Insertionsort, umgekehrt sortiert: Verschiebungen
- Selectionsort, vorsortiert: Vergleiche
Die Reihung {7, 7, 7, 7, 7, 7, 7, 7} wird mit der Java-Methode der Inhaltsseite sortiert. Bestimmen Sie die Anzahl der Vergleiche von Reihungselementen.
7 > 7 ist falsch — die Schleife endet sofort. Das ist der beste Fall: \(n-1=7\) Vergleiche und 0 Verschiebungen. Mit >= wäre es der ungünstigste Fall (28 Vergleiche, 28 Verschiebungen) — und das Verfahren nicht mehr stabil.7 > 7 wahr oder falsch?Ein Spiel speichert 1000 Highscores aufsteigend sortiert. Ein neuer Wert wird hinten angehängt; danach wird die ganze Reihung (1001 Elemente) neu sortiert. Beurteilen Sie die Aussagen.
Eine Lehrerin hat ihre Liste bereits alphabetisch geordnet: (Ali, 3) (Ben, 1) (Ella, 3) (Mia, 2) (Noah, 2). Nun sortiert sie mit Insertionsort aufsteigend nach der Note (Vergleich nur der Noten). Ermitteln Sie die Reihenfolge nach dem Sortieren.