# AlgoDat: Tutorium 1

## Aufgabe 1

#### a) **[1|2|3|4]**

InsertionSort

- Index: 1 2 3 4
$j=2$: **[1|2|3|4]**
$i=1: i=1 > 0$ und $A[1]=1 < key = 2$
*Vergleich: 1 und 2*

- Index: 1 2 3 4
$j=3:$ **[1|2|3|4]**
$i=2: i=2 > 0$ und $A[2]=2 < key = 3$
*Vergleich: 3 und 4*

- Index: 1 2 3 4
$j=4:$ **[1|2|3|4]**
$i=3: i=3 > 0$ und $A[3] < key = 4$
*Vergleich: 5 und 6*

$\Rightarrow$ Auf diesem Array werden
3 Vergleiche beim InsertionSort Algorithmus durchgeführt.

MergeSort:

Index: 1 2 3 4
Array: **[1|2|3|4]**
$l=1<r=4$
$m = 2$

| TeilArray: 1 2 | | TeilArray: 3 4 | |
| -------------- | --- | -------------- | --- |
| l=1<r=2 | | l=3<r=4 | |
| *Vergleich 1* | | *Vergleich 2* | |
| m=1 | | m=1 | |
|**TeilArray: 1**|**TeilArray: 2**|**TeilArray: 3**|**TeilArray: 4**|
| l=1=r |l=2=r |l=3=r |l=4=r |

| Merge(A=[1,2],l=1,m=1,r=2) | Merge(A=[3,4],l=3,m=3,r=4 |
| -------------------------- | ------------------------- |
| L[1]=1<R[1]=2 | L[1]=3<R[1]=4 |
| *Vergleich 3* | *Vergleich 4* |

| Merge(A=[1,2,3,4],l=1,m=2,r=4) |
| ------------------------------ |
| L[1]=1<R[1]=3 |
| *Vergleich 5* |
| L[2]=2<R[1]=3 |
| *Vergleich 6* |

$\Rightarrow$ Auf diesem Array werden 6 Vergleiche beim MergeSort Algorithmus durchgeführt.

#### b) *analog*

InsertionSort: 6 Vergleiche
MergeSort: 6 Vergleiche

## Aufgabe 2: Add per Schleife

Schleifeninvariante: $s=a+i-1$

#### 1.) Initialisierung

Zeige: Invariante ist beim 1.Schleifendurchlauf erfüllt.

Hier: klar, denn für $i=1$ gilt:
$s=a+i-1=a+1-1=a$

#### 2.) Aufrechterhaltung

Zeige: Wenn die Invariante vor dem $i.$ Schleifendurchlauf erfüllt ist,
dann auch vor dem $i+1.$

Hier: Vor dem $i.$ Durchlauf gilt INV,
d.h. $s=a+i-1$.
Dann wird $s$ mit $1$ addiert $\Rightarrow s=a+i$
Dann wird $i$ um $1$ erhöht $\Rightarrow s=a+i-1 \Leftarrow$ INV

#### 3.) Terminierung

Zeige:
Zusammengenommen ergeben Invariante und verletzte Schleifenbediengung die Korrektheit.

Hier: Verletzte Schleifenbedingung: $i>b$, also $i=b+1$.
Einsetzen von "$i=b+1$" in INV liefert $s=a+b$.

$\Rightarrow$ Der Algorithmus terminiert und liefert das korrekte Ergebnis.

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