MINT lernen

Abituraufgaben: Mergesort

Eine Bestenliste und zwei Lager voller Bestellungen — beide Male ist das Mischen sortierter Folgen der Schlüssel.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Bestenliste

14 BEAFB I–II

Ein Sportverein führt nach jedem Turnier eine Bestenliste. Die Punktzahlen stehen unsortiert in der Reihung punkte und sollen mit Mergesort (Quelltext aus dem Unterricht, mergesort(a, links, rechts) und mische(a, links, mitte, rechts)) aufsteigend sortiert werden.

Reihung punkte (Länge 6)
  1. Beschreiben Sie die Arbeitsweise von Mergesort nach dem Prinzip Teile und herrsche. (3 BE)
  2. Stellen Sie den Ablauf von mergesort(punkte, 0, 5) grafisch dar: erst alle Zerlegungen bis zu den Einzelelementen, dann alle Mischvorgänge mit ihrem Ergebnis. (5 BE)
  3. Geben Sie für den letzten Aufruf von mische an, welche Elemente verglichen werden, und nennen Sie die Anzahl der Vergleiche. (2 BE)
  4. Erläutern Sie am Beispiel der Bestenliste, was „stabil“ bedeutet und warum Mergesort durch a[i] <= a[j] in mische stabil ist. Die Spieler seien vorher alphabetisch sortiert. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
Teilen, rekursiv sortieren, mischen — und der Basisfall.
Hinweis zu Aufgabe b)
mitte = (0 + 5) / 2 = 2: Die Hälften haben je drei Elemente und werden ungleich weitergeteilt.
Hinweis zu Aufgabe c)
Die Hälften vor dem letzten Mischen sind 27, 38, 41 und 12, 30, 45.
Hinweis zu Aufgabe d)
Was passiert mit zwei Spielern gleicher Punktzahl?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Der Bereich wird bei mitte ohne Vergleich halbiert (Teilen). Beide Hälften werden rekursiv mit Mergesort sortiert (Herrschen). Die sortierten Hälften werden durch Mischen zu einer sortierten Folge verbunden (Zusammenführen). Bereiche mit höchstens einem Element sind bereits sortiert (Basisfall).

Erwartungshorizont zu Aufgabe b)
Zerlegen: [41, 27, 38, 12, 45, 30] [41, 27, 38] [12, 45, 30] [41, 27] [38] [12, 45] [30] [41] [27] [12] [45] Mischen: [41] + [27] → [27, 41] [27, 41] + [38] → [27, 38, 41] [12] + [45] → [12, 45] [12, 45] + [30] → [12, 30, 45] [27, 38, 41] + [12, 30, 45] → [12, 27, 30, 38, 41, 45]

Die linke Hälfte wird vollständig sortiert, bevor die rechte beginnt.

Erwartungshorizont zu Aufgabe c)

Vergleiche: 27–12 (12), 27–30 (27), 38–30 (30), 38–45 (38), 41–45 (41); danach ist die linke Hälfte leer und 45 wird ohne Vergleich übernommen. 5 Vergleiche.

Erwartungshorizont zu Aufgabe d)

Stabil heißt: Elemente mit gleichem Sortierschlüssel behalten ihre bisherige Reihenfolge. Haben z. B. „Ali“ und „Mara“ beide 38 Punkte und steht Ali in der alphabetischen Liste vorn, steht er auch nach dem Sortieren nach Punkten vor Mara — bei gleicher Punktzahl bleibt die Liste alphabetisch. In mische liegt das früher stehende Element immer in der linken Hälfte; mit <= wird bei Gleichheit das linke zuerst übernommen. Mit < käme das rechte zuerst, und die Reihenfolge wäre vertauscht.

2

Bestellungen zusammenführen

16 BEAFB II–III

Ein Online-Shop hat zwei Lager. Jedes Lager liefert seine Bestellnummern des Tages als aufsteigend sortierte Reihung (x und y, verschieden lang). Die Zentrale braucht eine gemeinsame, aufsteigend sortierte Liste. An manchen Tagen sollen alle 50 000 Bestellungen des Monats in einer unsortierten Reihung neu sortiert werden.

  1. Implementieren Sie eine Methode static int[] mischeListen(int[] x, int[] y), die eine neue, aufsteigend sortierte Reihung mit allen Elementen beider Reihungen zurückgibt. (5 BE)
  2. Bestimmen Sie die kleinste und die größte mögliche Zahl von Vergleichen Ihrer Methode für Reihungen der Längen \(p\) und \(q\) und geben Sie für beide Fälle ein Beispiel an. (3 BE)
  3. Leiten Sie her, dass Mergesort für \(n = 2^k\) Elemente höchstens \(n\cdot\log_2 n\) Vergleiche benötigt. (4 BE)
  4. Beurteilen Sie, ob für das Sortieren der 50 000 Bestellungen Mergesort oder Selectionsort verwendet werden sollte. Berücksichtigen Sie Laufzeit und Speicherbedarf. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
Zwei Indizes i, j, eine Ergebnisreihung der Länge x.length + y.length, danach die Reste.
Hinweis zu Aufgabe b)
Wenige Vergleiche: Alle Elemente der einen Reihung sind kleiner als alle der anderen. Viele: Die Elemente wechseln sich ab.
Hinweis zu Aufgabe c)
Jede Ebene des Mergesort-Baums kostet höchstens \(n\) Vergleiche. Wie viele Ebenen gibt es?
Hinweis zu Aufgabe d)
Setzen Sie \(n = 50\,000\) in \(n\log_2 n\) und in \(\frac{n(n-1)}{2}\) ein.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
static int[] mischeListen(int[] x, int[] y) {
    int[] erg = new int[x.length + y.length];
    int i = 0, j = 0, k = 0;
    while (i < x.length && j < y.length) {
        if (x[i] <= y[j]) {
            erg[k] = x[i];
            i++;
        } else {
            erg[k] = y[j];
            j++;
        }
        k++;
    }
    while (i < x.length) {
        erg[k] = x[i];
        i++;
        k++;
    }
    while (j < y.length) {
        erg[k] = y[j];
        j++;
        k++;
    }
    return erg;
}

Beispiel: mischeListen({3, 8, 15}, {1, 9, 10, 20}) liefert 1, 3, 8, 9, 10, 15, 20.

Erwartungshorizont zu Aufgabe b)

Minimum: \(\min(p, q)\) Vergleiche — alle Elemente der kürzeren Reihung sind kleiner als das erste der anderen, z. B. {1, 2} und {5, 6, 7}: 2 Vergleiche. Maximum: \(p + q - 1\) — jeder Vergleich legt ein Element ab, und das letzte Element wird ohne Vergleich übernommen, z. B. {1, 3, 5} und {2, 4, 6}: 5 Vergleiche.

Erwartungshorizont zu Aufgabe c)

Mischen zweier Hälften mit zusammen \(n\) Elementen kostet höchstens \(n - 1 < n\) Vergleiche: \(V(n) \le 2V\!\left(\frac{n}{2}\right) + n\), \(V(1) = 0\).

Einsetzen: \(V(n) \le 4V\!\left(\frac{n}{4}\right) + 2n \le \dots \le 2^k V\!\left(\frac{n}{2^k}\right) + k\cdot n = n\cdot V(1) + n\log_2 n = n\log_2 n\), da \(2^k = n\) und \(k = \log_2 n\). Anschaulich: \(\log_2 n\) Ebenen mit jeweils höchstens \(n\) Vergleichen.

Erwartungshorizont zu Aufgabe d)

Mergesort: höchstens \(50\,000\cdot\log_2 50\,000 \approx 50\,000\cdot15{,}6 \approx 7{,}8\cdot10^5\) Vergleiche. Selectionsort: \(\frac{50\,000\cdot49\,999}{2}\approx1{,}25\cdot10^9\) Vergleiche — rund 1600-mal so viele. Mergesort braucht eine Hilfsreihung mit 50 000 Plätzen (bei int rund 200 kB), Selectionsort keinen Zusatzspeicher. Der Speicher ist bei heutigen Rechnern kein Problem, der Zeitunterschied dagegen groß: Mergesort ist klar vorzuziehen. Nur bei extrem knappem Speicher wäre Selectionsort vertretbar — dann eher ein in-place-Verfahren wie Quicksort.