Rückblick
Quicksort und Mergesort lösen dieselbe Aufgabe wie die Verfahren aus der Einführungsphase – nur eben nicht in n², sondern in n · log n Schritten. Der Unterschied ist keine Kleinigkeit: Er entscheidet darüber, ob eine Million Datensätze in Sekunden oder in Stunden sortiert sind.
Das kann ich jetzt
- Ich kann Quicksort erklären: Pivot wählen, aufteilen, rekursiv weitermachen. (6.1)
- Ich kann Mergesort erklären: halbieren, sortieren, verschmelzen. (6.2)
- Ich kann das Verschmelzen zweier sortierter Folgen selbst implementieren. (6.2)
- Ich kann beide Verfahren nach Aufwand und Speicherbedarf vergleichen.
- Ich kann begründen, warum beide dem Prinzip Teilen und Herrschen folgen.
Gemischte Aufgaben
Aufgabe 1: Schritt für Schritt
Gegeben ist die Folge 7 2 9 4 1 8 3.
a) Führ Quicksort auf Papier durch. Wähle als Pivot jeweils das letzte Element des betrachteten Abschnitts. Notiere nach jeder Aufteilung den Zustand des Feldes und markiere, welcher Abschnitt als Nächstes drankommt.
b) Führ Mergesort auf Papier durch. Zeichne den Baum des Halbierens nach unten und das Verschmelzen nach oben.
c) Wie tief wird die Rekursion bei Mergesort für sieben Elemente? Wie tief bei Quicksort in deiner Rechnung aus a)?
d) Bei welchem der beiden Verfahren hängt die Tiefe von den Daten ab? Warum?
Tipp zu a)
Nach der Aufteilung steht das Pivot an seinem endgültigen Platz: Links davon liegt alles Kleinere, rechts alles Größere. Beide Seiten sind für sich noch unsortiert – auf sie wird dasselbe Verfahren angewandt.
Aufgabe 2: Verschmelzen
Schreib die Methode int[] verschmelze(int[] pLinks, int[] pRechts), die zwei bereits sortierte Felder zu einem sortierten Feld zusammenführt.
a) Erkläre in Worten, warum dafür ein einziger Durchlauf über beide Felder genügt – und warum das bei unsortierten Feldern nicht ginge.
b) Implementiere die Methode.
c) Was passiert, wenn eines der Felder früher zu Ende ist als das andere? Wie fängst du das ab?
d) Wie viele Vergleiche braucht das Verschmelzen von zwei Feldern der Längen n und m höchstens?
e) Warum braucht Mergesort im Gegensatz zu Quicksort zusätzlichen Speicher?
Tipp: Drei Zeiger
Du brauchst drei Positionen: eine im linken Feld, eine im rechten und eine im Ergebnis. In jedem Schritt vergleichst du die beiden vordersten Elemente, übernimmst das kleinere und rückst nur dort weiter.
Aufgabe 3: Beurteilen
a) Ein Feld ist bereits sortiert. Was tut Quicksort mit dem letzten Element als Pivot? Wie viele Ebenen entstehen, und wie viel Aufwand ist das insgesamt?
b) Wie lässt sich dieser Fall entschärfen? Nenne zwei Möglichkeiten.
c) Zwei Datensätze haben denselben Sortierschlüssel. Ein Verfahren heißt stabil, wenn ihre ursprüngliche Reihenfolge erhalten bleibt. Warum ist Stabilität bei einer Tabelle wichtig, die man nacheinander nach zwei Spalten sortiert?
d) Für 1000 Elemente braucht ein n²-Verfahren rund 500 000 Vergleiche. Wie viele braucht ein n · log n-Verfahren ungefähr? Um welchen Faktor unterscheiden sie sich?
e) Wann würdest du trotzdem Sortieren durch Einfügen wählen?