MINT lernen

Abituraufgaben: Insertionsort

Zwei Aufgaben auf Abiturniveau: Insertionsort darstellen und durchspielen, eine sortierte Rangliste pflegen und den Aufwand abschätzen.

Dein Fortschritt:
0 / 0 Aufgaben
1

Bestellungen nach Uhrzeit

AFB I–II

Ein Online-Shop erhält Bestellungen aus mehreren Lagern; die Eingangszeiten (in Minuten nach Öffnung) kommen ungeordnet an. Bevor die Bestellungen bearbeitet werden, sortiert die Software die Reihung zeit aufsteigend mit Insertionsort.

Reihung zeit vor dem Sortieren
zeit95040113022537041105
  1. Beschreiben Sie das Prinzip von Insertionsort.
  2. Stellen Sie Insertionsort als Struktogramm dar (Zwischenspeicher x, Laufindex j).
  3. Wenden Sie Ihr Verfahren auf die Reihung zeit an: Geben Sie für jede Runde x, die Anzahl der Verschiebungen und Vergleiche sowie die Reihung danach in einer Tabelle an, und nennen Sie die Summen.

Hinweise

Hinweis zu Aufgabe a)
Denken Sie an Spielkarten, die man einzeln aufnimmt.
Hinweis zu Aufgabe b)
Äußere Zählschleife ab Index 1; innere Schleife mit zusammengesetzter Bedingung.
Hinweis zu Aufgabe c)
Der Vergleich, der die innere Schleife beendet, zählt mit. Bei j = -1 endet sie ohne Vergleich.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Die Reihung wird in einen sortierten Teil (links, anfangs nur das erste Element) und einen unsortierten Teil geteilt. In jeder Runde wird das erste Element des unsortierten Teils zwischengespeichert. Von rechts nach links rücken alle Elemente des sortierten Teils, die größer sind, um einen Platz nach rechts; in die entstandene Lücke wird das gespeicherte Element eingefügt. Nach \(n-1\) Runden ist alles sortiert.

Erwartungshorizont zu Aufgabe b)

Wichtig: Bedingung j ≥ 0 vor dem Zugriff auf a[j]; Einfügen erst nach der Schleife.

Erwartungshorizont zu Aufgabe c)
ixVerschiebungenVergleichezeit danach
1401140 95 | 130 25 70 110
21300140 95 130 | 25 70 110
3253325 40 95 130 | 70 110
4702325 40 70 95 130 | 110
51101225 40 70 95 110 130

Summe: 10 Vergleiche und 7 Verschiebungen (zum Vergleich: Selectionsort bräuchte 15 Vergleiche).

2

Eine Rangliste, die sortiert bleibt

AFB II–III

Ein Online-Spiel führt eine Rangliste. Die Punktzahlen stehen in einer Reihung punkte der Länge 1000; belegt sind die ersten anzahl Plätze, und zwar aufsteigend sortiert. Jeder neue Punktestand wird mit folgendem Verfahren eingetragen:

  1. Es gilt anzahl = 5 und punkte beginnt mit 120, 145, 170, 210, 260. Ein neuer Wert 150 wird eingetragen. Analysieren Sie das Verfahren an diesem Beispiel: Geben Sie die Anzahl der Vergleiche und Verschiebungen, die belegten Plätze danach und den Rückgabewert an, und kennzeichnen Sie, für welche neuen Werte der Aufwand am größten ist.
  2. Implementieren Sie das Verfahren als Java-Methode public static int einfuegen(int[] punkte, int anzahl, int wert). Ist die Reihung schon voll, soll nichts verändert und anzahl zurückgegeben werden.
  3. Täglich kommen 10 000 neue Punktestände hinzu, die Liste enthält etwa 1000 Einträge. Variante A hängt jeden Wert hinten an und sortiert die ganze Liste mit Selectionsort neu, Variante B benutzt einfuegen. Schätzen Sie die Anzahl der Vergleiche pro Tag für beide Varianten ab.
  4. Mit der Bedingung punkte[j] > wert landet ein neuer Punktestand hinter gleich hohen älteren Einträgen, also in der aufsteigenden Liste auf einem höheren Rang. Ein Spieler fordert, dass bei Gleichstand der ältere Eintrag den höheren Rang behalten soll, und schlägt >= vor. Erörtern Sie diesen Vorschlag.

Hinweise

Hinweis zu Aufgabe a)
Tracetabelle mit j und punkte[j]; der Rückgabewert ist die neue Anzahl belegter Plätze.
Hinweis zu Aufgabe b)
Zuerst die Bedingung „voll“ prüfen: anzahl == punkte.length.
Hinweis zu Aufgabe c)
Selectionsort: \(\frac{n(n-1)}{2}\) je Sortierung; einfuegen: höchstens anzahl Vergleiche.
Hinweis zu Aufgabe d)
Wo landet ein neuer Wert bei Gleichstand mit >, wo mit >=? Was kostet die Änderung, was bewirkt sie?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
jpunkte[j]punkte[j] > 150?Aktion
4260japunkte[5] ← 260
3210japunkte[4] ← 210
2170japunkte[3] ← 170
1145neinSchleife endet

4 Vergleiche, 3 Verschiebungen; punkte[2] ← 150. Belegt: 120, 145, 150, 170, 210, 260; Rückgabe 6. Am größten ist der Aufwand für Werte, die kleiner als alle vorhandenen sind: Dann rücken alle anzahl Einträge, es gibt anzahl Vergleiche. Ist der Wert mindestens so groß wie der letzte, genügt ein Vergleich.

Erwartungshorizont zu Aufgabe b)
public static int einfuegen(int[] punkte, int anzahl, int wert) {
    if (anzahl == punkte.length) {
        return anzahl;                      // Liste voll
    }
    int j = anzahl - 1;
    while (j >= 0 && punkte[j] > wert) {
        punkte[j + 1] = punkte[j];
        j--;
    }
    punkte[j + 1] = wert;
    return anzahl + 1;
}

Bewertet werden: Behandlung der vollen Reihung, Reihenfolge der Teilbedingungen, Verschieben nach rechts, Einfügen nach der Schleife, Rückgabe der neuen Anzahl.

Erwartungshorizont zu Aufgabe c)

Variante A: je Wert \(\frac{1000\cdot999}{2}\approx5\cdot10^{5}\) Vergleiche, pro Tag \(\approx10\,000\cdot5\cdot10^{5}=5\cdot10^{9}\). Variante B: je Wert höchstens 1000 Vergleiche, pro Tag höchstens \(10^{7}\). Variante B ist mindestens etwa 500-mal sparsamer; im Mittel (neuer Wert in der Mitte) sogar etwa 1000-mal.

Erwartungshorizont zu Aufgabe d)

Pro: Mit >= rücken auch gleich hohe Einträge nach rechts, der neue Wert landet vor ihnen — bei Gleichstand behält der ältere Eintrag den höheren Rang, wie gefordert. Das entspricht dem üblichen Fairnessprinzip „wer zuerst da war“. Contra: Bei vielen gleichen Punktzahlen entstehen zusätzliche Verschiebungen (Aufwand steigt, im Extremfall alle Einträge). Die bisherige Variante ist das stabile Einfügen; die neue ist aber ebenfalls eindeutig und konsistent, solange sie überall gleich verwendet wird. Alternativ könnte man einen Zeitstempel als zweites Kriterium speichern. Fazit (begründet, z. B.): Der Vorschlag erfüllt die Anforderung mit geringem Mehraufwand und ist zu übernehmen.