---
# System prepended metadata

title: Liste der Algorithmen
tags: [Algorithmen und Datenstrukturen, Informatik, Uni]

---

# Liste der Algorithmen

[TOC]

# Sortieralgorithmen

## Vergleich

|             | InsertionSort  | MergeSort             | HeapSort              | QuickSort           |
| ----------- | -------------- | --------------------- | --------------------- | ------------------- |
| Worst-Case  | $\Theta (n^2)$ | $\Theta(n\cdot logn)$ | $\Theta(n\cdot logn)$ | $\Theta (n^2)$      |
| Avg-Case    | $\Theta (n^2)$ | $\Theta(n\cdot logn)$ | $\Theta(n\cdot logn)$ | $\Theta (n \log n)$ |
| Best-Case   | $\Theta (n)$   | $\Theta(n\cdot logn)$ | $\Theta(n\cdot logn)$ | $\Theta (n \log n)$ |
| in situ$^1$ | true           | false                 | true                  | true                |
| stabil$^2$  | true           | true                  | false                 | false               |

$^1$ Ein in situ-Algorithmus benötigt nur O(1) extra Speicher.
(in situ = in place)  
$^2$ Sortieralgorithmus heißt stabil,
wenn er gleiche Schlüssel in Ursprungsreihenfolge belässt.

## InsertionSort

```java=
InsertionSort(int[ ] A)
for j = 2 to A.length do
  key = A[j]
  i = j − 1 
  while i > 0 and A[i] > key do
    A[i + 1] = A[i]
    i = i − 1
  A[i + 1] = key
```

## MergeSort

```java=
MergeSort(int[ ] A, int l = 1, int r = A.length)
  if l < r then 
    m = (l + r)/2
    MergeSort(A,l,m)
    MergeSort(A,m + 1, r)
    Merge(A,l,m, r)
```

```java=
Merge(int[ ] A, int l, int m, int r)
n1 = m − l + 1; n2 = r − m
L = new int[1..n1 + 1]; R = new int[1..n2 + 1]
L[1...n1] = A[l..m]
R[1..n2] = A[m + 1..r]
L[n1 + 1] = R[n2 + 1] = ∞ 
i = j = 1 
for k = l to r do 
  if L[i] ≤ R[j] then 
    A[k] = L[i] 
    i = i + 1 
  else 
    A[k] = R[j]
    j = j + 1
```

## Heap(Sort)

```java=
HeapSort(A)
BuildMaxHeap(A)
for i = A.length downto 2 do 
  A[i] = ExtractMax()
```

```java=
BuildMaxHeap(feld A)
A.heap-size = A.length
for i = A.length/2 downto 1 do
  MaxHeapify(A, i)
```

```java=
MaxHeapify(feld A, index i)
l = left(i); r = right(i)
if l ≤ A.heap-size and A[l] > A[i] then 
  largest = l
else largest = i
if r ≤ A.heap-size and A[r] > A[largest] then
  largest = r
if largest != i then
  swap(A, i, largest)
  MaxHeapify(A, largest)
```

```java=
FindMax()
return A[1]
```

```java=
ExtractMax()
if A.heap-size < 1 then
  error “Heap underflow”
max = A[1]
A[1] = A[A.heap-size] 
A.heap-size − − 
MaxHeapify(A, 1) 
return max
```

```java=
IncreaseKey(index i, priorität p)
if p < A[i] then 
  error “prio. too small”
A[i] = p 
while i > 1 and A[parent(i)] < A[i] 
  swap(A, i, parent(i))
  i = parent(i)
```

```java=
Insert(priorität p)
A.heap-size + +
if A.heap-size > A.length then 
  error ... 
A[A.heap-size] = −∞ 
IncreaseKey(A.heap-size, p)
```

## QuickSort

```java=
QuickSort(A, l = 1, r = A.length)
if l < r then 
  m = Partition(A, l, r)
  QuickSort(A, l ,m − 1)
  QuickSort(A,m + 1, r)
```

```java=
Partition(int[ ]A, int l, int r)
pivot = A[r]
i = l 
for j = l to r − 1 do 
  if A[j] ≤ pivot then 
    Swap(A, i, j) 
    i = i + 1 
Swap(A, i, r)
return i
```

```java=
RandomizedPartition(A, l, r)
i =Random(l, r) 
Swap(A[r],A[i]) 
return Partition(A, l, r)
```

### Das Auswahlproblem

Idee: Finde gutes Pivot-Element in Θ(n) Zeit.
Dann läuft QuickSort in Θ(n log n) Zeit.

```java=
Minimum(Feld A)
min = A[1]
for i = 2 to A.length do
  if min > A[i] then 
  min = A[i] 
return min
```

- MinMax(FeldA)

```java=
if(A[1]<A[2])
  min = A[1]
  max = A[2]
else
  min = A[2]
  max = A[1]
for i = 3 to i = A.length - 1 do
  if(A[i]<A[i+1])
    if(min > A[i])
      min = A[i]
    if(max < A[i+1])
      max = A[i+1]
  else
    if(min > A[i+1])
      min = A[i+1]
    if(max < A[i])
      max = A[i]
  i + 2
```

## CountingSort

CountingSort(Feld A, B, int k)
```java=
C[0,...,k] = 0
for j=1 to A.length do
  C[A[j]] = C[A[j]]+1
for i=1 to k do
  C[i] = C[i]+C[i-1]
for j=A.length downto 1 do
  B[C[A[j]]] = A[j]
  C[A[j]] = C[A[j]]-1
```
Laufzeit: O(n+k0)

![CountingSort](https://i.imgur.com/dN7ENfC.png =400x)

## RadixSort

LSDRadixSort(Feld A, int d)
```java=
for i=1 to d do
  sortiere A stabil nach der i-ten Stelle
```
//LSD: least-signifikant digit

Laufzeit: O(d*Laufzeit Sortierverfahren)  
Beispiel: Geburtstage sortieren, je 1x nach Tag, Monat, Jahr (d = 3)

## BucketSort

BucketSort(A)
```java=
n = A.length
B[0,...,n-1] Listen
for j=1 to n do
  Insert(A[j]) in B[n*A[j]]
for i=0 to n-1 do
  sortiere Liste B[i]
füge B[0],...,B[n-1] aneinander
kopiere B nach A[1,...,n]
```
Laufzeit: Abhängig von der Eingabe und vom Sortieralgorithmus  
$T_{BS}=\Theta (n) + \sum_{i=0}^{n-1}T_{Sortieren}(n_i)$

![BucketSort](https://i.imgur.com/RwdmUfJ.png =300x)

# Datenstrukturen

## Stack (Stapel)

![Stack](https://i.imgur.com/gSWwu6e.png =400x)
```java=
key[] A
int top
```

verwaltet sich ändernde Menge nach LIFO-Prinzip

- boolean Empty()
```java=
if( == null)
  return true
else
  return false
```
- Push(key k)
```java=
top = top++ 
A[top]=k
```
- key Pop()
```java=
if Empty()
  error "underflow"
else
  top--
  return A[top + 1]
```
- key Top()
```java=
if Empty()
  error "underflow"
else
  return A[top]
```

## Queue (Schlange)

![Queue](https://i.imgur.com/loXbyi6.png =400x)

```java=
key[] A
int head
int tail
```
verwaltet sich ändernde Menge nach FIFO-Prinzip

- boolean Empty()
```java=
if(head == tail)
  return true
else
  return false
```
- Enqueue(key k)
```java=
A[tail]=k
if(tail == A.length)
  tail = 1
else
  tail++
```
- key Dequeue()
```java=
k = A[head]
if(head == A.length)
  head = 1
else
  head++
return k
```

## Liste

![](https://i.imgur.com/5AYm24R.png =500x)

```java=
head = nil
```
- ptr Search(key k)
```java=
x = head
while (x != nil && x.key != k do)
  x = x.next
return x
```
- ptr Insert(key k)
```java=
x = new Item(k, head)
if(head != nil)
  head.prev = x
else
  head = x
return x
```
- Item (key k, ptr p)
```java=
x.key = k
x.prev = nil
x.next = p
```
- Delete(ptr x)
```java=
if(x.prev != nil)
  x.prev.next = x.next
else
  head = x.next
if(x.next != nil)
  x.next.prev = x.prev
```

## Hashing

### HashDa

![Hashing](https://i.imgur.com/wX6mme8.png =500x)

- HashDa(int m)

```java=
T = new ptr[0,...,m-1]
for j=0 to m-1 do
  T[j] = nil
```

- ptr Insert(key k, info i)

```java=
T[k] = new info(i)
```

- Delete(key k)

```java=
Speicher freigeben, auf den T[k] zeigt
T[k] = nil
```

- ptr Search(key k)

```java=
return T[k]
```

### Hashing mit Verkettung

![HashChain](https://i.imgur.com/6qDHTgs.png =500x)
- Hashfunktion h
- HashChaining(int m)
```java=
T = new ptr[0,...,m-1]
for j=0 to m-1 do
  T[j] = List
```
- ptr Insert(key k, info i)
```java=
return T[h(k)].Insert(k) //List.Insert(k)
```
- Delete(key k)
```java=
T[h(k)].Delete(k) //List.Delete(k)
```
- ptr Search(key k)
```java=
return T[h(k)].Search(k) //List.Search(k)
```

### Hashing mit offener Adressierung

![HashingOA](https://i.imgur.com/DCz1tXj.png =500x)

- HashOA(int m)
```java=
T = new ptr[0,...,m-1]
for j=0 to m-1 do
  T[j] = nil
```
- ptr Insert(key k)
```java=
i=0
repeat
  j=h(k,i)
  if T[j] == nil then
    T[j]=k
    return j
  else
    i++
until i == m
error "table overflow"
```
- Delete(key k)
```java=
T[Search(k)]=del // beim Suchen: belegter Eintrag, beim Einfügen: freier Eintrag
```
- ptr Search(key k)
```java=
i=0
repeat
  j=h(k,i)
  if T[j] == k then
    return j
  else
    i++
until i == m || T[j] == nil
return nil
```

## Bäume

### Binäre Suchbäume

![binärer Suchbaum](https://i.imgur.com/IM3AxzB.png =600x)  

h(T) = Höhe des Baums T =
$\begin{cases} 0 & \text{falls Baum = Blatt}\\
1+max\{h(T_l),h(T_r)\} & \text{sonst} \end{cases}$

![binSearchTree](https://i.imgur.com/RBYqjZx.png =400x)

- BinSearchTree()

```java=
Node root = nil
```

- Node(key k, Node par)

```java=
key = k
p = par
right = left = nil
```

- Node Search(key k)

```java=
//rekursiv
Node x = root
if x == nil or x.key == k then
  return x
if k < x.key then
  return Search(k, x.left)
else
  return Search(k, x.right)
```

```java=
//iterativ
Node x = root
while x != nil and x.key != k do
  if k < x.key then
    x = x.left
  else
    x = x.right
return x
```

- Node Minimum()

```java=
Node x = root
if x == nil then 
  return nil
while x.left != nil do
  x = x.left
return x
```

- Node Maximum()

```java=
Node x = root
if x == nil then 
  return nil
while x.right != nil do
  x = x.right
return x
```

- Node Successor(Node x)

![Node Successor](https://i.imgur.com/oVSo5IQ.png =400x)

```java=
if x.right != nil then
  return Minimum(x.right)
y = x.p
while y != nil and x == y.right do
  x = y
  y = y.p
return y

```

- Node Predecessor(Node x)  
analog

- Node Insert(key k)

![Insert Node](https://i.imgur.com/iauDToE.png)

```java=
y = nil
x = root
while x != nil do
  y = x
  if k < x.key then
    x = x.left
  else
    x = x.right
z = new Node(k, y)
if y == nil then
  root = z
else
  if k < y.key then
    y.left = z
  else
    y.right = z
return z
```

- Delete(key k)
  - z hat keine Kinder.  
![Fall 1](https://i.imgur.com/XDXzrsf.png =300x)  
Falls z linkes Kind von z.p ist, setze z.p.left = nil; sonst umgekehrt.
Lösche z.
  - z hat genau ein Kind x.  
![Fall 2](https://i.imgur.com/sOUhgjp.png =300x)  
Setze den Zeiger von z.p, der auf z zeigt, auf x.
Setze x.p = z.p.
Lösche z.
  - z hat zwei Kinder.  
![Fall 3](https://i.imgur.com/sF51f7a.png =300x)  
Setze y = Successor(z) und z.key = y.key.
Lösche y. (Fall 1 oder 2!)

### AVL-Bäume (Balanciermethode: nach Höhe)

- Tiefe des Teilbaums $d(T)$
- Balancegrad $bal(v) := d(T_l) − d(T_r)\in \{-1,0,1\}$
![bal(v)](https://i.imgur.com/DtG2uVE.png)
- ptr Search(key k), ptr Minimum(), ptr Maximum(),
ptr Predecessor(ptr x), ptr Successor(ptr x) wie zuvor
- ptr Insert(key k, info i):
  - Einfügen wie zuvor
  - Suchpfad merken
  - den Suchpfad entlang nach oben neu ausbalancieren:
    - Fall 1: vor dem Einfügen $bal(v) = 1 \Rightarrow bal(v)=0$  
![Insert1](https://i.imgur.com/SmBnyAg.png =400x)
    - Fall 2: vor dem Einfügen $bal(v) = 0 \Rightarrow bal(v)=-1, d(T)++$
    - Fall 3: vor dem Einfügen $bal(v) = -1 \Rightarrow bal(v)=-2$
      - Fall 3.1: Der rechte Teilbaum von v hängt außen zu tief
![Insert3.1](https://i.imgur.com/CNSUhNw.png =500x)  
$\Rightarrow bal(v)=0$
      - Fall 3.2: Der rechte Teilbaum von v hängt innen zu tief
![Insert3.2.1](https://i.imgur.com/l5HOPiT.png =500x)  
![Insert3.2.2](https://i.imgur.com/F3dPywN.png =500x)
$\Rightarrow bal(v)=0$
- ptr Delete(key k)
  - Löschen wie zuvor
  - Suchpfad merken
  - den Suchpfad entlang nach oben neu ausbalancieren

### 2-3-Bäume

![2-3-Baum](https://i.imgur.com/SmvjsSv.png)

- Search(z)
  - Falls z < x suche im ersten Teilbaum.
  - Falls z > x und y nicht existiert, suche im zweiten Teilbaum.
  - Falls z > x, y existiert und z < y, suche im zweiten Teilbaum.
  - Falls z > x, y existiert und z > y, suche im dritten Teilbaum.
  - Wird ein nil-Zeiger erreicht, brich die Suche erfolglos ab und gib nil zurück.
  - Speichere den Suchpfad auf einem Stapel (Stack) ab.
  - Laufzeit: O(d) = O(log n).
- Insert(z)
  - Search(z)
  - Betrachte Knoten mit dem nil-Zeiger am Ende der erfolglosen Suche
  - Fall 1: Knoten enthält nur ein Datum x:
![Insert2-3 1](https://i.imgur.com/X0pbkiz.png =500x)
  - Fall 2: Knoten enthält 2 Daten x,y:
![Insert2-3 2](https://i.imgur.com/Ig8skgu.png)
  - Laufzeit: O(log n)
- Delete(z)
  - Search(z)
  - Falls x nicht in einem Blatt liegt: Vertausche x und Successor
  - Lösche x (und evtl. nil-Zeiger) $\Rightarrow$ der Zeiger p auf x hängt zu hoch
    - Fall 1: benachbarter Zeiger q zeigt auf Knoten mit zwei Daten
![2-3Delete 1](https://i.imgur.com/bUJFjeP.png =400x)
    - Fall 2: benachbarter Zeiger q zeigt auf Knoten mit einem Datum
      - Fall 2.1: a enthält noch ein zweites Datum a'
![2-3Delete2.1](https://i.imgur.com/zusmX42.png =400x)
      - Fall 2.2: q zeigt auf einen Knoten mit einem Datum y und a ist das einzige Datum.
![2-3Delete2.2](https://i.imgur.com/G8jL4ig.png =400x)

### Durchlaufstrategien

- TreeWalk/PostorderTreeWalk

```java=
1. RecurseLeft() 
2. RecurseRight() 
3. Do something
```

- PreorderTreeWalk

```java=
1. Do something
2. RecurseLeft() 
3. RecurseRight() 
```

- InorderTreeWalk

```java=
1. RecurseLeft() 
2. Do something
3. RecurseRight() 
```

## Graphen

### Breitensuche

### Tiefensuche



###### tags: `Algorithmen und Datenstrukturen` `Informatik` `Uni`