Search and Sort

(Suchen und Sortieren)

Suchalgorithmen

• Linear Search (jedes Element einmal anschauen)
• Laufzeit: $\Theta(n)$
• Binary Search (wenn sortiert)
  • Rekursiv, Liste halbieren, schauen, ob die Mitte das gesuchte Element ist. Wenn nein, dann schauen ob die Mitte größer oder kleiner als das gesuchte Element ist und dementsprechend alles von vorne mit nur der linken/rechten Seite.
  • $T(n) = T\left(\frac{n}{2}\right) + c$
  • Laufzeit $\Theta(\log n)$

Jedes vergleichsbasierte Suchen braucht im schlechtesten Fall $\Omega(\log(n))$ Vergleiche. [[Beweis, vergleichsbasiertes Suchen in log(n)]]

Für vergleichsbasiertes Sortieren ist es $n \log(n)$.

Warum folgt aus $T\left( \frac{n}{2} \right)$ eine Laufzeit von $\log(n)$?

$$
\begin{align*}
T(n) &= T!\left(\frac{n}{2}\right) + c \\
&= \bigl(T!\left(\tfrac{n}{4}\right) + c\bigr) + c \quad &\text{(Konstanten irrelevant)}\\
&= T!\left(\tfrac{n}{8}\right) + 3c \\
&\;\;\vdots \\
&= T!\left(\tfrac{n}{2^k}\right) + kc
\end{align*}
$$

$\frac{n}{2^k}=1 \implies 2^k=n \implies k=\log_{2}(n)$

Entscheidungsbaum

• Jeder Knoten ist ein Vergleich
• jeder Knoten hat höchstens zwei Kinder, ja oder nein
• Ganz oben “Wurzel”
• Unteste Ebene: “Blätter” sind Rückgabewerte
• Gesamtzahl der Blätter mindestens $n+1$ (jeder Outcome + nicht gefunden)
• Anzahl der Vergleiche im schlechtesten Fall ist die Höhe des Baumes
• Entscheidungsbaum mit Tiefe h, hat eine Anzahl von Blättern > n!, die maximale Anzahl an Blättern ist $2^h$. Also gilt $2^h \geq n! \implies n \geq \log_{2}(n!) \geq \Omega(n \log(n))$. Tiefe des Binärbaumes ist log die Anzahl der Knoten.

Sortieralgorithmen, Einführung

• Bubble Sort
  • Wenn das Element größer als das darauffolgende ist, werden die beiden getauscht. Nach einer Iteration ist also das größte Element ganz hinten.
  • Laufzeit $\Theta(n^2)$
• Selection Sort
  • größtes Element ans Ende (oder kleinstes Element an den Anfang)
  • Vertauschungen $\Theta(n)$, aber Vergleiche $\Theta(n^2)$
  • Also Laufzeit $\Theta(n^2)$
• Insertion Sort
  • jedes neue Element von rechts an die richtige Stelle im sortierten Array ganz links einfügen
  • Invariante: $I(j)$: nach $j$ Iterationen ist das Teilarray $A[1…j]$ (also die ersten $j$ Elemente) sortiert. Das heißt nicht, dass sie an der richtigen Stelle sind (aber sie sind halt sortiert).
  • Vergleiche: Wir nehmen ein neues Element und suchen die richtige Stelle im sortierten Teilarray, um es einzusetzen. Da Binary Search in $O(\log(n))$ läuft, und wir hier alle Elemente außer das erste einmal einsortieren müssen, haben wir $\sum_{j=2}^{n} \log(n)=n\log(n)$.
  • Vertauschungen: Sagen wir, das Array ist verkehrt sortiert, z.B. $\boxed{54321}$, dann wird im ersten Schritt 4 in das sortierte Teilarray hinzugefügt, und 5 muss 1 nach rechts verschoben werden. Dann kommt 3, und 4 und 5 müssen jew. 1 nach rechts verschoben werden, etc. Am Ende haben wir also $\frac{n(n-1)}{2}$ Vertauschungen. Also:
  • Vergleiche $\Theta(n \cdot log(n))$, aber immer noch $\Theta(n^2)$ Vertauschungen
  • Also Laufzeit $\Theta(n^2)$
• Merge Sort
  • teile in Hälften, sortiere rekursiv und kombiniere (divide and conquer)
  • Achtung, extra Space (Hilfsarray)
  • $\Theta(n \log n)$
• Quicksort
  • Wiederhole rekursiv:
    • Wähle ein Pivotelement p (z.B. das letzte Element des Arrays).
    • Alle Elemente kleiner als p nach links, alle größer als p nach rechts (links und rechts ist nicht sortiert)
  • Invariante: Nach jeder Aufteilung gilt: Alle Elemente links vom Pivot sind kleiner oder gleich, alle rechts größer.
  • Problem entsteht, wenn das Pivotelement z.B. den größten oder kleinsten Wert der Liste hat (z.B. Array schon sortiert) → worst case
  • Laufzeit:
    • Best Case: $O(n \log n)$
    • Worst Case: $O(n^2)$
• Heap Sort
  • Selection Sort, aber mit effizienter Suche nach dem größten Element durch Nutzung eines Max-Heaps
  • Heap: von oben nach unten und links nach rechts gelesen sind die Elemente wie im Array. Alle child Elemente sind kleiner als das Parent Element.
  • Ablauf:
    1. Wandle das Array in einen Heap um
    2. Wiederhole:
       • Entferne das Maximum (Wurzel)
       • Platziere es am Ende des Arrays
       • Stelle die Heap-Bedingung wieder her (versickere)
         • Tausche parent mit größerem child solange, bis Heap Bedingung gilt.
  • Laufzeit: $O(n \log n)$

Übersicht

Achtung, bspw. die Laufzeit von Mergesort ist ja auch in $O(n^2)$