# 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:
Die Mannschaft Nr. 1 mit dem Wert 95 hat gewonnen.
Nun betrachten wir alle Mannschaften,
die direkt gegen Mannschaft Nr. 1 verloren haben.
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:
Der Gewinner der 2. Runde, Mannschaft Nr. 2 ist damit insgesamt Zweitplatzierter.

## Aufgabe 2

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:

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

Es gilt:

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

$\Leftrightarrow$

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

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`