---
# System prepended metadata

title: 'Algorithmen und Datenstrukturen, Blatt 5'
tags: [Algorithmen und Datenstrukturen, Informatik, Uni]

---

# Algorithmen und Datenstrukturen, Blatt 5

## Aufgabe 1

- Ermittle Gewinner (typisches K.o.-Turnier benötigt dazu n-1 Spiele)
- Notiere dabei für jede Mannschaft X alle Mannschaften, die gegen X verloren haben,
z.B. in Arraylist V_X.
- Nimm die Gewinner-Mannschaft G. Es haben maximal $log_2(n)$ Mannschaften
direkt gegen G verloren.
Das bedeutet, alle anderen Mannschaften haben gegen andere Mannschaften verloren.
Daraus folgt, dass es $O(log_2(n))$ mögliche Zweitplazierte gibt.
- Nimm alle V_G möglichen Zweitplatzierten.
- Ermittle Gewinner unter V_G (K.o.-Turnier: $O(log_2(n)-1)=O(log n)$ Spiele).
Dieser ist dann der Zweitplatzierte.
- Es werden mit dieser Strategie also nur n+O(log n) Spiele benötigt.

Beispiel zum besseren Verständnis:

Wir nehmen 8 Mannschaften.
Jeder Mannschaft ordnen wir einen Zahlenwert zu, der ihr Können beschreibt.  
Wir ermitteln den Gewinner:
![Spiel 1](https://i.imgur.com/q7I4v2E.png)
Die Mannschaft Nr. 1 mit dem Wert 95 hat gewonnen.
Nun betrachten wir alle Mannschaften,
die direkt gegen Mannschaft Nr. 1 verloren haben.
![Verlierer](https://i.imgur.com/8B4zbun.png)
Das sind die Mannschaften mit den Werten 94, 86 und 92,
also die Mannschaften Nr. 2, 4 und 7.
In einer weiteren Spielrunde
werden nun diese Mannschaften gegeneinander antreten:  
![2. Runde](https://i.imgur.com/SbYdYHk.png =x200)  
Der Gewinner der 2. Runde, Mannschaft Nr. 2 ist damit insgesamt Zweitplatzierter.

## Aufgabe 2

```java=
Radix Sort(A,d)
for i=1 to d do
  sortiere A stabil nach der i-ten Stelle
```

### 2a)

Beweis per Induktion über d:

Induktionsanfang: d=1:  
Die Elemente haben nur eine Stelle,
d.h. die for-Schleife wird genau einmal aufgerufen und
das Array korrekt sortiert.  
Induktionsannahme:
Für ein beliebiges, aber festes d sortiert LSD-RadixSort korrekt.  
Induktionsschluss: d $\Rightarrow$ d+1:  

```java=
Radix Sort(A,d+1)
for i=1 to d+1 do
  sortiere A stabil nach der i-ten Stelle
```

Es gilt:  

```java=
Radix Sort(A,d+1)
for i=1 to d+1 do
  sortiere A stabil nach der i-ten Stelle
```

$\Leftrightarrow$

```java=
Radix Sort(A,d+1)
for i=1 to d do
  sortiere A stabil nach der i-ten Stelle
sortiere A stabil nach der d+1-ten Stelle
```

Der Teil

```java=
Radix Sort(A,d+1)
for i=1 to d do
  sortiere A stabil nach der i-ten Stelle
```

ist nach Induktionsannahme bereits sortiert.
Wir müssen also nur zeigen, dass "sortiere A stabil nach der d+1-ten Stelle"
die bisherige Korrektheit nicht verletzt und A anschließend sortiert ist.  
Nehmen wir uns nun zwei direkt aufeinanderfolgende Elemente aus A,
z.B. die Zahlen $X:=x_1x_2...x_k$ und $Y:=y_1y_2...y_k$,
wobei $x_1$, bzw. $y_1$ die erste Ziffer von $X$, bzw. $Y$ darstellt,
$x_2$, bzw. $y_2$ die zweite Ziffer von $X$, bzw. $Y$, und so weiter.
Es muss gelten $k=d+1$.
Da es sich hier um das LSD(=least signifikant digit)-RadixSort-Verfahren handelt,
ist d+1 hier die wichtigste Stelle, im Fall von Zahlen also die erste Ziffer,
d die zweitwichtigste, also die zweite Ziffer und so weiter.
Da laut Induktionsannahme die Stellen 1 - d sortiert sind,
bedeutet dies für unsere Zahlen $X$ und $Y$,
dass sie bereits nach den letzten d Ziffern sortiert sind.
Wenn also im Moment gilt $A[X]<A[Y]$, dann bedeutet das $x_2...x_k \leq y_2...y_k$
und es müssen noch die Ziffern $x_1$ und $y_1$ sortiert werden.  

- $x_1 \leq y_1$: Da bereits $A[X]<A[Y]$ gilt, wird nichts vertauscht (stabiles Sortierverfahren).
Die Reihenfolge stimmt,
da $x_1 \leq y_1 \land x_2...x_k \leq y_2...y_k \Rightarrow X \leq Y$.
- $x_1 > y_1$: $X$ und $Y$ werden vertauscht.
Es gilt also $Y < X$,
da die wichtigsten Stellen $x_1, y_1$ ausschlaggebend für
den Zahlenwert insgesamt sind.
Z.B. ist 23 > 19, da die Zehnerstelle ausschlaggebend ist und es gilt 2 > 1,
obwohl die Einerstelle 3 < 9.  
LSD-RadixSort sortiert also korrekt.
  
### 2c)

UNI, AUF, EIS, FUN, WAS, KUH, FBI, POL, WER  
nach dem ersten Durchgang, sortiert nach i=3:  
AUF,KUH, UNI, FBI, POL, FUN, WER, EIS, WAS  
nach dem zweiten Durchgang, sortiert nach i=2:  
WAS, FBI, WER, EIS, UNI, POL, AUF, KUH, FUN  
nach dem dritten Durchgang, sortiert nach i=1:  
AUF, EIS, FBI, FUN, KUH, POL, UNI, WAS, WER  

## Aufgabe 3

### 3a)

Wenn wir zwei Listen X und Y, beide sortiert,
in die Ergebnisliste A mergen wollen, gibt es zwei Möglichkeiten:

- A[i] und A[i+1] sind beide in Liste X, bzw. beide in Liste Y.
Da die Liste bereits sortiert ist,
müssen diese beiden Elemente nicht mehr miteinander verglichen werden.
- A[i] und A[i+1] sind in unterschiedlichen Listen.
Da allerdings zunächst nicht bekannt ist,
ob das kleinere Element das in Liste X oder das in Liste Y ist,
da beide Listen unabhängig voneinander sortiert wurden,
müssen diese beiden Elemente miteinander verglichen werden.
Dies gilt auch für gleiche Elemente, da das im Vorfeld nicht klar ist.

### 3b)

Im Worst-Case sind die Elemente aus der Ergebnisliste A
abwechselnd in den Listen X und Y abgespeichert.

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