Dreißig Übungen zu Quicksort — vom Zerlegen am Pivot bis zu den Eingaben, die ihn ausbremsen.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Ü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.
A1
Quicksort im Vergleich
AFB IMix
Gib alle Aussagen an, die für Quicksort (Pivot = letztes Element) zutreffen.
Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Das Pivot landet nach dem Zerlegen genau zwischen den kleineren und den größeren Werten — dort bleibt es. Quicksort tauscht auch weit entfernte Elemente und ist deshalb nicht stabil. Wo geteilt wird, bestimmt das Pivot, nicht die Mitte; \(\frac{n(n-1)}{2}\) Vergleiche fallen nur im ungünstigsten Fall an.
Ansatz: Vergleiche mit Mergesort: Wo steckt die Arbeit, wo wird geteilt?
Weiter: Drei Aussagen übertragen Eigenschaften anderer Verfahren falsch auf Quicksort.
A2
Was beim Zerlegen passiert
AFB I
Beschreibe den Ablauf von zerlege(a, links, rechts), indem du die Lücken füllst.
Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück. Achtung: 2 Wörter bleiben übrig.
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 .
Nach dem Zerlegen stehen links von grenze nur Werte ≤ Pivot, rechts nur größere. Gemischt wird bei Mergesort, nicht bei Quicksort.
Ansatz: Lies die Schleife in zerlege Zeile für Zeile.
Weiter: Die Rückgabe von zerlege ist die Position des Pivots.
A3
Zerlegen in Einzelschritten
AFB I
Gegeben ist int[] w = {29, 64, 11, 47, 83, 35};. Wendezerlege(w, 0, 5) an: Trage für jedes k das Ergebnis des Vergleichs und den Wert von grenze danach ein.
Fülle alle Felder aus und prüfe dann. Enter in einem Feld prüft ebenfalls. Wahrheitswerte als wahr oder falsch.
k
w[k]
w[k] ≤ 35
grenze danach
0
29
1
64
2
11
3
47
4
83
Rückgabe
Nach der Schleife wird 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.
Ansatz: Das Pivot ist w[5] = 35. grenze startet bei 0.
Weiter: Nur bei „wahr“ wird getauscht und grenze erhöht.
