Mergesort: Übungen – Informatik Leistungskurs

A1

Stimmt's? — Eigenschaften von Mergesort

AFB I

Gib für jede Aussage über Mergesort an, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.

Aussage 1 von 5

Mergesort ist schnell und stabil, bezahlt das aber mit Speicher für die Hilfsreihung.

Ansatz: Denke an die drei Schritte und daran, wo verglichen wird.

Weiter: Stabil heißt: Gleiche Werte behalten ihre Reihenfolge.

A2

Wie das Mischen funktioniert

AFB I

Beschreibe das Mischen zweier sortierter Hälften, 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.

Zwei stehen auf den Anfängen der beiden sortierten Hälften. Das der beiden Elemente kommt in die , dann rückt sein Zeiger vor. Ist eine Hälfte leer, wird der der anderen ohne übernommen. Am Ende wird die Hilfsreihung in den Bereich .

Das Pivot gehört zu Quicksort. Beim Mischen wird immer das kleinere Front-Element übernommen — so entsteht die aufsteigende Folge.

Ansatz: Folge dem Ablauf im Quelltext von mische: zwei Indizes, eine Schleife, zwei Rest-Schleifen, Zurückkopieren.

Weiter: Sortiert wird aufsteigend — welches Element muss dann vorne stehen?

A3

Zwei Hälften mischen

AFB I

Die sortierten Hälften sind 6, 19, 33 und 4, 21, 25, 40. Wende das Mischen an: Trage in jeder Zeile den übernommenen Wert ein und gib die Zahl der Vergleiche an.

Fülle alle Felder aus und prüfe dann. Enter in einem Feld prüft ebenfalls.

Vergleich	a[i]	a[j]
1	6	4
2	6	21
3	19	21
4	33	21
5	33	25
6	33	40
Rest	leer	40
Vergleiche

Nach dem sechsten Vergleich ist die linke Hälfte leer; 40 wird ohne Vergleich angehängt. Ergebnis: 4, 6, 19, 21, 25, 33, 40 — mit 6 Vergleichen bei 7 Elementen.

Ansatz: In jeder Zeile gewinnt der kleinere der beiden Werte.

Weiter: Die Zeile „Rest“ zählt nicht als Vergleich.

A4

Die Aufrufreihenfolge

AFB II

mergesort(a, 0, 3) wird aufgerufen. Stelle dar, in welcher Reihenfolge die Aufrufe von mergesort und mische beginnen, indem du die Karten ordnest.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.

1mergesort(a, 0, 3)

2mergesort(a, 0, 1)

3mergesort(a, 0, 0)

4mergesort(a, 1, 1)

5mische(a, 0, 0, 1)

6mergesort(a, 2, 3)

7mergesort(a, 2, 2)

8mergesort(a, 3, 3)

9mische(a, 2, 2, 3)

10mische(a, 0, 1, 3)

Die linke Hälfte wird komplett sortiert (einschließlich ihres mische), bevor die rechte beginnt. Das letzte mische verbindet die beiden sortierten Hälften.

Ansatz: Jeder Aufruf führt seine drei Zeilen der Reihe nach aus: links sortieren, rechts sortieren, mischen.

Weiter: Ein Aufruf mit einem Element endet sofort — danach geht es beim Aufrufer weiter.

A5

Vergleiche im ungünstigsten Fall

AFB II

Mergesort sortiert 16 Elemente. Beim Mischen zweier Hälften mit je \(p\) Elementen fallen höchstens \(2p - 1\) Vergleiche an. Berechne die Werte für den ungünstigsten Fall.

Rechne die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.

Anzahl der Misch-Ebenen: Ebenen
Ebene 2 (vier Mal 2 + 2 Elemente): Vergleiche
Ebene 4 (einmal 8 + 8 Elemente): Vergleiche
Alle Ebenen zusammen: Vergleiche

Die vier Ebenen kosten höchstens 8 · 1 = 8, 4 · 3 = 12, 2 · 7 = 14 und 1 · 15 = 15 Vergleiche, zusammen 49. Die Schranke \(n\log_2 n = 64\) wird also sicher eingehalten; genau gilt \(n\log_2 n - n + 1 = 49\).

Ansatz: \(\log_2 16 = 4\).

Weiter: Ebene 1: 8 Mischvorgänge mit je 1 + 1 Elementen, Ebene 3: 2 Mischvorgänge mit je 4 + 4.

A6

Welches Verfahren ist gemeint?

AFB II Mix

Ordne jedem Verfahren die Eigenschaft zu, die es von den anderen unterscheidet.

Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.

Selectionsort und Insertionsort stammen aus Kapitel 2: Der eine vergleicht stur alle Paare, der andere nutzt Vorsortierung. Mergesort ist das einzige der drei schnellen Verfahren, das zusätzlichen Speicher braucht.

Ansatz: Überlege, was jedes Verfahren besonders gut oder besonders schlecht kann.

Weiter: Nur eines der Verfahren sucht, statt zu sortieren.

A7

Fehler im Mischen

AFB II

Eine Mitschülerin hat mische(a, links, mitte, rechts) geschrieben; sie soll stabil aufsteigend mischen. Überprüfe den Quelltext und markiere die drei fehlerhaften Zeilen.

In diesem Text stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.

Mit || läuft die Hauptschleife weiter, obwohl eine Hälfte leer ist, und greift über ihr Ende hinaus. Mit j = mitte gehört a[mitte] zu beiden Hälften und wird doppelt übernommen.

Ansatz: Prüfe die Startwerte der Zeiger und die Schleifenbedingung.

Weiter: Eine Zeile verletzt nur die Stabilität, nicht die Sortierung.

A8

Schon sortiert?

AFB III Trick

Mergesort erhält die bereits aufsteigend sortierte Reihung 1, 2, 3, …, 16. Ermittle die Anzahl der Vergleiche.

Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.

Auch sortierte Daten werden vollständig geteilt und gemischt. Beim Mischen ist jedes linke Element kleiner als jedes rechte: Es werden nur die \(p\) linken Elemente verglichen, dann kommt die rechte Hälfte als Rest. Jede Ebene kostet \(\frac{n}{2} = 8\) Vergleiche, bei 4 Ebenen also 32 — nicht 0 und nicht 15.

Ansatz: Mergesort prüft nicht vorher, ob schon sortiert ist.

Weiter: Wie viele Vergleiche braucht das Mischen von 1, 2 und 3, 4?

A9

Welches Verfahren nimmst du?

AFB III

Entscheide für jede Situation, welches Sortierverfahren am besten passt.

Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).

1Mergesort

2Insertionsort

3Selectionsort

Mergesort: große Datenmengen, Garantie \(n\log_2 n\), stabil — und Mischen funktioniert auch blockweise von der Festplatte. Insertionsort ist bei fast sortierten Daten fast linear. Selectionsort vertauscht höchstens \(n - 1\)-mal — gut, wenn Schreiben teuer ist.

Ansatz: Frage jeweils: Wie viele Daten? Vorsortiert? Was ist teuer — Vergleichen, Schreiben oder Speicher?

Weiter: Das „Mischen“ großer Dateien ist die ursprüngliche Anwendung von Mergesort.

A10

Absteigend sortieren

AFB III

Mergesort soll absteigend und weiterhin stabil sortieren. Verändere die Methode mische, indem du die Lücken füllst.

Wähle in jedem Menü den passenden Eintrag und prüfe dann alle auf einmal.

static void mische(int[] a, int links, int mitte, int rechts) {
    int[] hilf = new int[rechts - links + 1];
    int i = links, j = , k = 0;
    while (i <= mitte  j <= rechts) {
        if (a[i]  a[j]) { hilf[k] = a[i]; i++; }
        else { hilf[k] = a[j]; j++; }
        k++;
    }
    while (i <= mitte) { hilf[k] = a[i]; i++; k++; }
    while (j <= rechts) { hilf[k] = a[j]; j++; k++; }
    for (k = 0; k < hilf.length; k++) a[links + k] = hilf[];
}

Absteigend heißt: das größere Front-Element zuerst. Mit >= gewinnt bei Gleichheit weiterhin das linke Element — stabil. Mit > wäre die Folge zwar absteigend, aber nicht stabil. hilf beginnt bei Index 0, der Zielbereich bei links.

Ansatz: Nur der Vergleich bestimmt die Sortierrichtung — alles andere bleibt wie beim aufsteigenden Mischen.

Weiter: Stabil bleibt es, wenn bei Gleichheit das linke Element gewinnt.

Übungen: Mergesort

Übungsaufgaben