Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.
Gib alle Aussagen an, die für Quicksort (Pivot = letztes Element) zutreffen.
Beschreibe den Ablauf von zerlege(a, links, rechts), indem du die Lücken füllst.
Das ist das letzte Element des Bereichs. Die Variable grenze markiert das Ende des Teils mit Werten, die oder gleich dem Pivot sind. Jedes Element wird einmal mit dem Pivot ; ist es nicht größer, wird es an die Stelle grenze und grenze rückt vor. Zum Schluss kommt das Pivot an die Stelle grenze — dort steht es .
grenze nur Werte ≤ Pivot, rechts nur größere. Gemischt wird bei Mergesort, nicht bei Quicksort.zerlege Zeile für Zeile.zerlege ist die Position des Pivots.Gegeben ist int[] w = {29, 64, 11, 47, 83, 35};. Wende zerlege(w, 0, 5) an: Trage für jedes k das Ergebnis des Vergleichs und den Wert von grenze danach ein.
wahr oder falsch.| k | w[k] | w[k] ≤ 35 | grenze danach |
|---|---|---|---|
| 0 | 29 | ||
| 1 | 64 | ||
| 2 | 11 | ||
| 3 | 47 | ||
| 4 | 83 | ||
| Rückgabe |
w[2] mit dem Pivot getauscht: 29, 11, 35, 47, 83, 64. Das Pivot 35 steht an Index 2 — davor die zwei kleineren Werte, dahinter die drei größeren.w[5] = 35. grenze startet bei 0.grenze erhöht.Im günstigsten Fall halbiert das Pivot jeden Bereich exakt, dann gilt \(V(n) = (n-1) + 2\cdot V\!\left(\frac{n-1}{2}\right)\) mit \(V(1) = 0\). Berechne die Werte.
- günstigster Fall \(V(3) =\) Vergleiche
- günstigster Fall \(V(7) =\) Vergleiche
- günstigster Fall \(V(15) =\) Vergleiche
- ungünstigster Fall für \(n = 15\): Vergleiche
Ermittle für jeden Aufruf den Rückgabewert von zerlege.
links plus die Anzahl der Werte ≤ Pivot im Bereich. Beim letzten Aufruf zählt nur der Bereich 2…5 mit 8, 2, 4, 7: zwei kleinere Werte, also 2 + 2 = 4.links.Ein Mitschüler hat Quicksort mit dem letzten Element als Pivot implementiert. Überprüfe den Quelltext und markiere die zwei fehlerhaften Zeilen.
a[rechts].a[grenze] getauscht wird?Quicksort (Pivot = letztes Element) erhält die schon sortierte Reihung 1, 2, …, 1000. Bestimme die Anzahl der Vergleiche.
Quicksort (Pivot = letztes Element, Code aus dem Unterricht) erhält die Reihung {5, 5, 5, 5, 5, 5, 5, 5}. Analysiere den Ablauf und gib die Anzahl der Vergleiche an.
a[k] <= pivot?Beurteile für jede Eingabe, ob Quicksort mit dem letzten Element als Pivot günstig (etwa \(n\log_2 n\)) oder ungünstig (etwa \(\frac{n^2}{2}\)) arbeitet.
Um sortierte Eingaben zu entschärfen, soll das mittlere Element des Bereichs Pivot werden, ohne den Rest von zerlege zu ändern. Verändere die Methode, indem du die Lücken füllst.
static int zerlege(int[] a, int links, int rechts) {
tausche(a, , ); // Mitte nach hinten
int pivot = a[rechts];
int grenze = links;
for (int k = links; k < ; k++) {
if (a[k] <= pivot) { tausche(a, grenze, k); grenze++; }
}
tausche(a, grenze, rechts);
return ;
}
rechts / 2 wäre nur für links = 0 die Mitte. Bei sortierter Eingabe ist das mittlere Element der Median: jeder Bereich wird halbiert, Tiefe und Vergleiche sinken auf \(\log_2 n\) bzw. etwa \(n\log_2 n\).rechts.links und rechts ab.