MINT lernen

Rekursive Verfahren beurteilen

Quicksort ist meist der Schnellste — warum stürzt er dann ausgerechnet bei schon sortierten Daten ab?

1

Laufzeiten vergleichen

  • Kriterien:Laufzeit (Vergleiche) im besten, mittleren und ungünstigsten Fall · Zusatzspeicher · Rekursionstiefe · Stabilität.
  • Wachstum:entscheidend ist, wie der Aufwand mit \(n\) wächst — nicht der Wert für ein kleines \(n\).
  • \(n\log_2 n\):doppelte Datenmenge → gut doppelte Arbeit. Für \(n = 10^6\) rund \(2\cdot10^7\) Vergleiche.
  • \(n^2\):doppelte Datenmenge → vierfache Arbeit. Für \(n = 10^6\) rund \(5\cdot10^{11}\) Vergleiche.
  • Doppelte Arbeit:Rekursion ist nur dann effizient, wenn Teilprobleme sich nicht überschneiden — sonst werden dieselben Werte mehrfach berechnet.
Sortierverfahren im Vergleich
SelectionsortInsertionsortMergesortQuicksort
bester Fall\(\frac{n(n-1)}{2}\)\(n-1\)\(\approx\frac{n}{2}\log_2 n\)\(\approx n\log_2 n\)
mittlerer Fall\(\frac{n(n-1)}{2}\)\(\approx\frac{n^2}{4}\)\(\approx n\log_2 n\)\(\approx 1{,}39\,n\log_2 n\)
ungünstigster Fall\(\frac{n(n-1)}{2}\)\(\frac{n(n-1)}{2}\)\(\le n\log_2 n\)\(\frac{n(n-1)}{2}\)
ZusatzspeicherkonstantkonstantHilfsreihung \(n\)konstant
Rekursionstiefe——\(\approx\log_2 n\)\(\approx\log_2 n\) bis \(n\)
stabilneinjajanein

Lege die gemessenen Kurven übereinander: Schalte Verfahren ein und aus, wechsle zwischen zufälliger und sortierter Eingabe und zwischen „Vergleiche“ und „Rekursionstiefe“. Ziehe den Messpunkt auf der n-Achse (oder ←/→), um die Werte bei einem n abzulesen.

Kurven übereinander

Halte fest: Bei zufälligen Daten liegen Mergesort und Quicksort dicht an \(n\log_2 n\) und weit unter der Parabel von Selectionsort. Bei sortierter Eingabe deckt sich Quicksort (Pivot = letztes Element) exakt mit Selectionsort — und seine Rekursionstiefe wächst linear mit n.

2

Speicher und Aufrufstapel

  • Aufrufstapel:jeder noch nicht beendete Aufruf belegt einen Eintrag mit Parametern, lokalen Variablen und Rücksprungstelle.
  • Rekursionstiefe:größte Zahl gleichzeitig offener Aufrufe — sie bestimmt den Speicher auf dem Stapel, nicht die Gesamtzahl der Aufrufe.
  • Überlauf:der Stapel ist begrenzt; bei einigen Tausend bis Zehntausend offenen Aufrufen bricht Java mit StackOverflowError ab.
  • Mergesort:Tiefe nur \(\approx\log_2 n\), aber eine Hilfsreihung mit \(n\) Plätzen.
  • Quicksort:keine Hilfsreihung, aber Tiefe bis \(n\), wenn das Pivot ungünstig liegt.
  • Lineare Rekursion:ein Aufruf je Element (z. B. rekursive Summe) hat Tiefe \(n\) — eine Schleife ist dann meist besser.
static int tiefe = 0, maxTiefe = 0;          // aktuelle und größte Rekursionstiefe

static void quicksort(int[] a, int links, int rechts) {
    tiefe++;                                 // ein Aufruf mehr auf dem Stapel
    maxTiefe = Math.max(maxTiefe, tiefe);
    if (links < rechts) {
        int p = zerlege(a, links, rechts);   // zerlege wie in 3.3.3
        quicksort(a, links, p - 1);
        quicksort(a, p + 1, rechts);
    }
    tiefe--;                                 // Aufruf beendet
}
// n = 5000:    zufällig: 32     sortiert: 5000
// n = 100000:  sortiert → java.lang.StackOverflowError
Herleitung:
\(\dfrac{n}{2^{d}} \ge 1\)
Bedingung

Mergesort: Auf Ebene \(d\) sind die Bereiche \(\frac{n}{2^d}\) groß; geteilt wird, solange ein Bereich noch Elemente hat.

\(2^{d} \le n\)
\(\cdot\,2^{d}\)

Beide Seiten mit \(2^d\) multiplizieren.

\(d \le \log_2 n\)
\(\log_2\)

Höchstens \(\log_2 n\) Halbierungen, dazu der erste Aufruf.

\(\text{Tiefe} = \log_2 n + 1\)
Ergebnis

Für \(n = 2^{20}\approx10^6\): 21 offene Aufrufe. Quicksort auf sortierten Daten: \(n\) offene Aufrufe.

Merke

Beurteilen nach Laufzeit in allen drei Fällen, Zusatzspeicher, Rekursionstiefe und Stabilität · Mergesort: garantiert \(n\log_2 n\), Tiefe \(\log_2 n\), braucht \(n\) Zusatzspeicher · Quicksort: im Mittel am schnellsten, in-place, aber im ungünstigsten Fall \(\frac{n(n-1)}{2}\) Vergleiche und Tiefe \(n\).

3

Allgemeine Hinweise

Kleines n täuscht

Bei 8 Elementen braucht Selectionsort 28 Vergleiche, Mergesort bis zu 17 — kaum ein Unterschied. Ein Urteil über Verfahren gilt dem Wachstum für große n.

Immer alle drei Fälle nennen

„Quicksort ist schnell“ reicht in einer Beurteilung nicht. Gib an, für welche Eingaben welcher Aufwand entsteht, und nenne ein Beispiel für den ungünstigsten Fall.

Aufrufe ≠ Tiefe

Mergesort macht bei \(n\) Elementen \(2n - 1\) Aufrufe, aber nur etwa \(\log_2 n\) sind gleichzeitig offen. Für den Stapel zählt die Tiefe, für die Zeit die Gesamtarbeit.

Videos