Aufgabe $2$: Sortieralgorithmen $(2$ Punkte$)$

In der Vorlesung haben Sie verschiedene Algorithmen zur Sortierung von Folgen

kennengelernt, darunter den Mergesort, Quicksort, Insertion Sort und andere. Mergeund Quicksort haben beide eine mittlere Komplexit$$at von O$($n log n$),$ Bubblesort

hingegen von O$($n

$2$

$).$

$1.$ Begrunden Sie, wann und warum man dennoch den Bubblesort oder andere Ver$-$

fahren mit schlechterer mittlerer Komplexit$$at bevorzugen k$$onnte$.1$ P

$2.$ Geben Sie eine Beispielsequenz an$,$ welche sich mit dem Bubblesort in weniger

Vergleichsoperationen sortieren l$$asst als mit Merge$-$ bzw$.$ Quicksort. $1$ P

Aufgabe $3$: QuickSort $(4$ Punkte$)$

Im folgenden betrachten wir nur die Partitionierung von QuickSort.

a$)$ Welche Eigenschaften soll die Partitionierung besitzen? $1$ P

b$)$ Illustrieren Sie die Arbeitsweise des dabei verwendeten Unteralgorithmus partition aus der Vorlesung am Beispiel der Folge A $=[8,2,5,1,3,6,7,4],$ Pivot$=4$

$1$ P

c$)$ Bestimmen Sie die Laufzeit der Partitionierung im Landau$-$Kalkul f $$ ur den Fall, $$

dass die Eingabe$-$Folge aus n identischen Zahlen besteht. $1$ P

d$)$ Bestimmen Sie die Laufzeit von QuickSort im Landau$-$Kalkul f $$ ur den Fall, dass $$

die Eingabe$-$Folge aus n identischen Zahlen besteht $($Pivot $=$ letztes Element$)\mathrm{.}1$ PAufgabe $1$: Insertion Sort mit bin$$rer Suche $(5$ Punkte$)$

in der Vorlesung haben Sie sowohl Insertion Sort, als auch die bin$\backslash$bar $($a$)$ re Suche kennen$-$

selernt. Entwerfen Sie eine Variante von Insertion Sort, welche die Einf$$geposition

ines Elementes mithilfe einer bin$$ren Suche bestimmt. Prinzipiell soll die Imple$-$

nentation sich nach dem folgendem Pseudo$-$Code richten:

a$)$ Geben Sie Thren Algorithmus in Python an$.$

Durch die bina$$re Suche hat sich die Anzahl der Vergleiche ver$$ndert$.$

Wie viele Vergleiche werden insgesamt ${?}^1$ im Average$-$Case bei einem nor$-$

malen Insertion Sort, und wie viele bei diesem Insertion Sort ben$$tigt$?$

W$$hlen Sie jeweils mit Begrundung ans den folgenden Komplexit$$tsklassen:

$O(n^2),O(nlogn),O(n),O(logn)$

Bestimmen Sie die Worst Case Laufzeit von diesem Algorithmus in der Landau

Notation und geben Sie ein Beispiel an$.$

Bestimmen Sie die Best Case Laufzeit von diesem Algorithmus in der Landau

Notation und geben Sie ein Beispiel an$.$

e$)$ Wann sollte dieser Algorithmus in der Praxis dem normalem Insertion Sort vor$-$

gezogen werden?

${?}^3$ far den kempletten Algorit hmus and nicht nar far die ianere SchleibeAufgabe $1$: Insertion Sort mit bin$$rer Suche $(5$ Punkte$)$

in der Vorlesung haben Sie sowohl Insertion Sort, als auch die bin$\backslash$bar $($a$)$ re Suche kennen$-$

selernt. Entwerfen Sie eine Variante von Insertion Sort, welche die Einf$$geposition

ines Elementes mithilfe einer bin$$ren Suche bestimmt. Prinzipiell soll die Imple$-$

nentation sich nach dem folgendem Pseudo$-$Code richten:

a$)$ Geben Sie Thren Algorithmus in Python an$.$

Durch die bina$$re Suche hat sich die Anzahl der Vergleiche ver$$ndert$.$

Wie viele Vergleiche werden insgesamt ${?}^1$ im Average$-$Case bei einem nor$-$

malen Insertion Sort, und wie viele bei diesem Insertion Sort ben$$tigt$?$

W$$hlen Sie jeweils mit Begrundung ans den folgenden Komplexit$$tsklassen:

$O(n^2),O(nlogn),O(n),O(logn)$

Bestimmen Sie die Worst Case Laufzeit von diesem Algorithmus in der Landau

Notation und geben Sie ein Beispiel an$.$

Bestimmen Sie die Best Case Laufzeit von diesem Algorithmus in der Landau

Notation und geben Sie ein Beispiel an$.$

e$)$ Wann sollte dieser Algorithmus in der Praxis dem normalem Insertion Sort vor$-$

gezogen werden?

${?}^3$ far den kempletten Algorit hmus and nicht nar far die ianere Schleibe