# Algorithmen und Datenstrukturen: Blatt 04

## Aufgabe 1

$A:= [15|62|44|87|9|34|18|74|83|25|93|46|58]$

### 1a)

Aufruf von HeapSort

Aufruf von BuildMaxHeap
Aufruf von MaxHeapify(A,7):
$[15|62|44|87|9|34|18|74|83|25|93|46|58]$
Aufruf von MaxHeapify(A,6):
$[15|62|44|87|9|58|18|74|83|25|93|46|34]$
Aufruf von MaxHeapify(A,5):
$[15|62|44|87|93|58|18|74|83|25|9|46|34]$
Aufruf von MaxHeapify(A,4):
$[15|62|44|87|93|58|18|74|83|25|9|46|34]$
Aufruf von MaxHeapify(A,3):
$[15|62|58|87|93|44|18|74|83|25|9|46|34]$
Aufruf von MaxHeapify(A,6):
$[15|62|58|87|93|46|18|74|83|25|9|44|34]$
Aufruf von MaxHeapify(A,2):
$[15|93|58|87|62|46|18|74|83|25|9|44|34]$
Aufruf von MaxHeapify(A,5):
$[15|93|58|87|62|46|18|74|83|25|9|44|34]$
Aufruf von MaxHeapify(A,1):
$[93|15|58|87|62|46|18|74|83|25|9|44|34]$
Aufruf von MaxHeapify(A,2):
$[93|87|58|15|62|46|18|74|83|25|9|44|34]$
Aufruf von MaxHeapify(A,4):
$[93|87|58|83|62|46|18|74|15|25|9|44|34]$

Aufruf von A[13]=ExtractMax:
$[87|83|58|74|62|46|18|34|15|25|9|44|93]$
Aufruf von A[12]=ExtractMax:
$[83|74|58|34|62|46|18|44|15|25|9|87|93]$
Aufruf von A[11]=ExtractMax:
$[74|62|58|44|25|46|18|34|15|9|83|87|93]$
Aufruf von A[10]=ExtractMax:
$[62|44|58|34|25|46|18|9|15|74|83|87|93]$
Aufruf von A[9]=ExtractMax:
$[58|44|46|34|25|15|18|9|62|74|83|87|93]$
Aufruf von A[8]=ExtractMax:
$[46|44|18|34|25|15|9|58|62|74|83|87|93]$
Aufruf von A[7]=ExtractMax:
$[44|34|18|9|25|15|46|58|62|74|83|87|93]$
Aufruf von A[6]=ExtractMax:
$[34|25|18|9|15|44|46|58|62|74|83|87|93]$
Aufruf von A[5]=ExtractMax:
$[25|15|18|9|34|44|46|58|62|74|83|87|93]$
Aufruf von A[4]=ExtractMax:
$[18|15|9|25|34|44|46|58|62|74|83|87|93]$
Aufruf von A[3]=ExtractMax:
$[15|9|18|25|34|44|46|58|62|74|83|87|93]$
Aufruf von A[2]=ExtractMax:
$[9|15|18|25|34|44|46|58|62|74|83|87|93]$


#### 1b)

Das kleinste Element ist immer auf Blättern,
weil "Parent node" immer größer oder gleich sein muss.
Würde man nun einen Heap betrachten, dessen letzte Ebene "vollständig" ist,
der als genau $\sum_{i=0}^k 2^i$, $k = \mathbb{N}_0$ Elemente enthält,
so müsste das kleinste Element an den letzten $2^k$ Stellen im Array liegen.
Enthält der Heap nur $(\sum_{i=0}^k 2^i)-x$ Elemente, $x = \mathbb{N}_0$,
so befindet sich das kleinste Element an den letzten $2^k-x+(2^{k-1}-x/2)$ Stellen.

## Aufgabe 2


### 2a)

Zunächst gilt $i=1$. Da die Bedingung if $A[j] \leq$ pivot für immer erfüllt ist
(genauer: es ist immer $A[j]=pivot$ erfüllt)
und innerhalb der Bedingung $i=i+1$ gesetzt wird, gilt am Ende der for-Schleife $i=r-1$.
Dieses $i=r-1$ wird am Ende der Methode auch zurück gegeben.
Dadurch tritt der in der Vorlesung besprochene 1. Extremfall auf:
Das Element m in QuickSort ist immer das erste Element.
Deshalb gilt $T(n) \in \Theta (n^2)$.

### 2b)

Partition'(int[ ]A, int l, int r)
pivot = A[r]
q = l
Arraylist Same = []
for j = l to r − 1 do 
  if A[j] < pivot then 
    Swap(A, q, j) 
    q = q + 1
  if A[j] = pivot then
    Same.add(j)
Swap(A, q, r)
for j = 1 to Same.size() do
  Swap(A,q+j,Same.get(j))
t = q + Same.size()
return q,t

Die Idee hinter der Modifizierung ist,
dass die Methode zunächst alle Indizes der Elemente abspeichert,
die gleich dem Pivot-Element sind und
diese anschließend direkt hinter das Pivot-Element tauscht.

### 2c)

QuickSort'(A, l = 1, r = A.length)
if l < r then 
  q,t = Partition(A, l, r)
  QuickSort(A, l ,q − 1)
  QuickSort(A,t + 1, r)

Die Laufzeit von QuickSort für ein Array mit lauter gleichen Elementen
wurde in Aufgabe 2a) beantwortet.
Die Laufzeit von QuickSort' für ein Array mit lauter gleichen Elementen:
$T(n)=\Theta (n)$

## Aufgabe 3

### 3a)

Schleifeninvariante: $j \geq i+1$

i=1: Daraus folgt $j\geq 2$, was durch die Schleifenbedingung gegeben ist,
da $j$ von A.length zu $i+1$ runterzählt. $\Rightarrow$
Das Array enthält mindestens 2 Elemente, denn sonst bereits sortiert bzw leer.
Vor dem $j+1$. Schleifendurchlauf gilt $j=i+1$ und damit
gilt die Schleifeninvariante auch durch die Definition von "$\geq$".
Damit ist das Array bereits $i-mal$ durch-getauscht worden
und somit rückt nach jedem Durchgang das kleinste Element
nach der $i-$ten Stelle um eins nach vorne, bis es bei $i$ ist.
Sobald also gilt $j<i+1$ und die Schleife abgebrochen wird,
dass das kleinste Element nach $i$ an der $i$-ten Stelle
des Arrays ist und die Schleife wird abgebrochen.

### 3b)

### 3c)

Zeile 1: n
Zeile 2:$\sum_{i=1}^{n-1} i$
Zeile 3: $\sum_{i=1}^{n-1} i$
Zeile 4: $\sum_{i=1}^{n-1}i$

$\Rightarrow$ $T(n)=n \cdot\sum_{i=1}^{n-1} i
\cdot (2\cdot \sum_{i=1}^{n-1} i)$
und somit $T(n) = \Theta (n^3)$

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