Die Lagerverwaltung
14 BEAFB I–IIEine Lagerverwaltung sortiert die Lagerplatznummern offener Aufträge mit Quicksort (Quelltext aus dem Unterricht: quicksort(a, links, rechts) und zerlege(a, links, rechts) mit dem letzten Element als Pivot).
- Nennen Sie, was bei Quicksort den Schritten Teilen, Herrschen und Zusammenführen entspricht. (3 BE)
- Stellen Sie den Ablauf von
zerlege(lager, 0, 6)in einer Tracetabelle mit den Spaltenk,lager[k],lager[k] ≤ pivot,grenzeund Reihung dar. Geben Sie den Rückgabewert an. (5 BE) - Bestimmen Sie die beiden rekursiven Aufrufe nach dem ersten Zerlegen und die Gesamtzahl der Vergleiche
a[k] <= pivot, bislagersortiert ist. (3 BE) - Erklären Sie an einem selbst gewählten Beispiel mit vier Elementen, warum Quicksort nicht stabil ist. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Teilen: Zerlegen des Bereichs am Pivot in Werte ≤ Pivot und größere Werte; das Pivot kommt an seine endgültige Position. Herrschen: rekursives Sortieren der Bereiche links und rechts vom Pivot. Zusammenführen: entfällt, weil die Teile schon in der richtigen Reihenfolge liegen.
Erwartungshorizont zu Aufgabe b)
| k | lager[k] | lager[k] ≤ 29 | grenze | Reihung danach |
|---|---|---|---|---|
| 0 | 34 | falsch | 0 | 34, 18, 52, 7, 41, 25, 29 |
| 1 | 18 | wahr | 1 | 18, 34, 52, 7, 41, 25, 29 |
| 2 | 52 | falsch | 1 | 18, 34, 52, 7, 41, 25, 29 |
| 3 | 7 | wahr | 2 | 18, 7, 52, 34, 41, 25, 29 |
| 4 | 41 | falsch | 2 | 18, 7, 52, 34, 41, 25, 29 |
| 5 | 25 | wahr | 3 | 18, 7, 25, 34, 41, 52, 29 |
| — | Pivot | — | 3 | 18, 7, 25, 29, 41, 52, 34 |
Rückgabewert 3; das Pivot 29 steht endgültig an Index 3.
Erwartungshorizont zu Aufgabe c)
Folgeaufrufe: quicksort(lager, 0, 2) für 18, 7, 25 und quicksort(lager, 4, 6) für 41, 52, 34.
Vergleiche: erstes Zerlegen 6; Bereich 0…2 (Pivot 25): 2, danach 0…1 (Pivot 7): 1; Bereich 4…6 (Pivot 34): 2, danach 5…6 (Pivot 41): 1. Summe \(6 + 2 + 1 + 2 + 1 = 12\). Ergebnis 7, 18, 25, 29, 34, 41, 52.
Erwartungshorizont zu Aufgabe d)
Beispiel {5a, 9, 5b, 3}: Pivot 3, kein Wert ist ≤ 3, also tauscht zerlege das Pivot mit a[0]: {3, 9, 5b, 5a}. Damit steht 5a hinter 5b. Im Bereich 9, 5b, 5a ist 5a das Pivot; 5b ≤ 5a wird nach vorn getauscht, das Ergebnis ist 3, 5b, 5a, 9 — die ursprüngliche Reihenfolge der beiden 5er ist vertauscht. Ursache: zerlege tauscht über weite Entfernungen, ohne auf die Reihenfolge gleicher Werte zu achten.
Die sortierten Lieferscheine
16 BEAFB II–IIIEine Spedition sortiert jeden Abend ihre Lieferscheine nach Nummern. Die Scheine kommen fast immer schon in aufsteigender Reihenfolge an, weil sie in dieser Reihenfolge gedruckt werden. Seit die Spedition rund 100 000 Lieferscheine pro Abend hat, bricht das Java-Programm mit Quicksort (letztes Element als Pivot) mit einem StackOverflowError ab.
- Analysieren Sie das Verhalten von Quicksort bei einer aufsteigend sortierten Eingabe mit \(n\) Elementen: Anzahl der Vergleiche und Rekursionstiefe. (4 BE)
- Erläutern Sie, wie es zu dem
StackOverflowErrorkommt. (3 BE) - Implementieren Sie eine Methode
static int medianIndex(int[] a, int links, int rechts), die von den Indizeslinks,mitteundrechtsdenjenigen zurückgibt, dessen Wert der mittlere der drei ist. Geben Sie an, wiezerlegedamit ergänzt wird. (5 BE) - Beurteilen Sie, ob die Spedition das verbesserte Quicksort, Mergesort oder Insertionsort einsetzen sollte. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
rechts getauscht.Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Das Pivot ist immer das Maximum des Bereichs. Alle anderen Werte sind kleiner, der rechte Teil bleibt leer, der linke hat \(n - 1\) Elemente. Vergleiche: \((n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}\), für \(n = 100\,000\) also rund \(5\cdot10^9\). Die Aufrufe quicksort(a, 0, n−1), quicksort(a, 0, n−2), … sind alle gleichzeitig offen: Rekursionstiefe \(n\).
Erwartungshorizont zu Aufgabe b)
Jeder Aufruf legt einen Eintrag (Parameter, lokale Variablen, Rücksprungstelle) auf den Aufrufstapel, der erst beim Beenden des Aufrufs wieder frei wird. Bei sortierter Eingabe endet kein Aufruf, bevor der nächste, um eins kleinere begonnen hat — bis zu 100 000 Einträge gleichzeitig. Der Stapel ist begrenzt (typisch einige Tausend bis Zehntausend Einträge); ist er voll, bricht Java mit StackOverflowError ab.
Erwartungshorizont zu Aufgabe c)
static int medianIndex(int[] a, int links, int rechts) {
int mitte = (links + rechts) / 2;
int x = a[links], y = a[mitte], z = a[rechts];
if ((x <= y && y <= z) || (z <= y && y <= x)) {
return mitte;
}
if ((y <= x && x <= z) || (z <= x && x <= y)) {
return links;
}
return rechts;
}Ergänzung als erste Zeile von zerlege: tausche(a, medianIndex(a, links, rechts), rechts); — danach bleibt zerlege unverändert. Bei sortierter Eingabe ist der Median das mittlere Element; jeder Bereich wird halbiert. Für 100 000 sortierte Werte sinkt die gemessene Rekursionstiefe auf 17.
Erwartungshorizont zu Aufgabe d)
Verbessertes Quicksort: bei fast sortierten Daten etwa \(n\log_2 n\approx1{,}7\cdot10^6\) Vergleiche, Tiefe um 17, kein Zusatzspeicher — aber für speziell gebaute Eingaben bleibt ein quadratischer ungünstigster Fall möglich. Mergesort: garantiert höchstens \(n\log_2 n\) Vergleiche und Tiefe 18, braucht aber eine Hilfsreihung für 100 000 Werte (unkritisch). Insertionsort: bei fast sortierten Daten nur wenig mehr als \(n - 1\approx10^5\) Vergleiche, iterativ ohne Stapelproblem; liegen aber einzelne Scheine weit falsch, wächst der Aufwand stark. Empfehlung: Da die Daten fast immer sortiert ankommen, ist Insertionsort am schnellsten; wer eine Garantie für Ausnahmetage will, nimmt Mergesort. Das verbesserte Quicksort ist ebenfalls vertretbar. Andere begründete Entscheidungen sind möglich.