# 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)
## 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)$
# Datenstrukturen
## Stack (Stapel)
```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)
```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
```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
- 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
- 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
- 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
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()
```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)
```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)
```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.
Falls z linkes Kind von z.p ist, setze z.p.left = nil; sonst umgekehrt.
Lösche z.
- z hat genau ein Kind x.
Setze den Zeiger von z.p, der auf z zeigt, auf x.
Setze x.p = z.p.
Lösche z.
- z hat zwei Kinder.
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\}$
- 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$
- 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
$\Rightarrow bal(v)=0$
- Fall 3.2: Der rechte Teilbaum von v hängt innen zu tief
$\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
- 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:
- Fall 2: Knoten enthält 2 Daten x,y:
- 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
- Fall 2: benachbarter Zeiger q zeigt auf Knoten mit einem Datum
- Fall 2.1: a enthält noch ein zweites Datum a'
- Fall 2.2: q zeigt auf einen Knoten mit einem Datum y und a ist das einzige Datum.
### 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`
Sign in with Wallet
Connect another wallet