====== - Sortieralgorithmen & Rekursion in C# ======
===== - Einfache Sortieralgorithmen =====
==== - Theorie ====
In diesem Kapitel werden einige bekannte Sortieralgorithmen kurz beschrieben.
=== Selectionsort ===
Vergleiche das erste Element der Reihe nach mit allen anderen Elementen. Vertausche die beiden, wenn dasjenige rechts grösser ist als das erste Element. Danach weisst du, dass ganz links das kleinste Element steht. Wiederhole nun diese Schritte aber ausgehend vom zweiten Element, dann vom dritten ...
=== Bubblesort ===
Gehe Liste durch und vergleiche immer zwei benachbarte Elemente. Ist dasjenige rechts kleiner, so vertausche die beiden. Mache dies solange, bis die Liste sortiert ist.
=== Insertionsort ===
Beginne mit dem zweiten Element und vergleiche es mit dem ersten. Falls das zweite Kleiner ist, vertausche es. Nun sind die ersten beiden Elemente sortiert. Betrachte nun das dritte und füge es in der bereits sortierten Teilliste am korrekten Platz ein (einfügen = insert). Gehe weiter vierten Element usw.
==== - Auftrag 1 ====
Ziel ist, die oben beschriebenen Sortieralgorithmen in C# für Arrays (und nicht für Listen) zu implementieren. Erstelle ein C#-Projekt //SortingAlgorithms//, in welchem du sämtliche Aufträge zu Sortieralgorithmen lösen sollst.
**Vorgehen:**
1. Zuerst musst du den Algorithmus **verstehen**.
1. Wende den Algorithmus **auf Papier** auf eine kurze Beispielliste an.
1. Implementiere den Algorithmus.
=== Teil 1: Selectionssort ===
Implementiere den Selectionssort-Algorithmus.
++++Lösung|
public static void SelectionSort(int[] L)
{
for (int i = 0; i < L.Length; i++)
{
for (int j = i + 1; j < L.Length; j++)
{
if (L[j] < L[i])
{
int temp = L[j];
L[j] = L[i];
L[i] = temp;
}
}
}
}
++++
=== Teil 2: Bubblesort ===
Implementiere den Bubblesort-Algorithmus.
++++Lösung|
public static void Swap(int[] L, int i, int j)
{
int temp = L[i];
L[i] = L[j];
L[j] = temp;
}
public static void Bubblesort(int[] L)
{
bool isNotSorted = true;
while (isNotSorted)
{
isNotSorted = false;
for (int i = 0; i < L.Length - 1; i++)
{
if (L[i + 1] < L[i])
{
Swap(L, i, i+1);
isNotSorted = true;
}
}
if (!isNotSorted)
{
break;
}
}
}
++++
=== Teil 3: Insertionsort ===
1. Implementiere eine Funktion `public static int[] Insert(int[] A, int i, int j)`, welche ein Array und zwei Indizes (Zahlen) entgegennimmt, wobei i>j. Das Element an Position i wird an Position j eingefügt. Wird das Array `{10,11,12,13,14,15}` mit i=4 und j=2 übergeben, so wird das Array `{10,11,14,12,13,15}` zurückgegeben.
1. Implementiere den Insertionsort-Algorithmus. Verwende dazu die oben implementierte Insert-Funktion.
++++Lösung|
public static int[] Insert(int[] A, int i, int j)
{
// insert element i at position j < i,
// shift all others to right
// RAISE EXCEPTION if j > i
if (j > i)
{
throw new Exception();
}
// INSERT
int el_i = A[i];
for (int k = i - 1; k >= j; k--)
{
A[k + 1] = A[k];
}
A[j] = el_i;
return A;
}
public static void Insertionsort(int[] L)
{
for (int i = 1; i < L.Length; i++)
{
for (int j = 0; j < i; j++)
{
if (L[i] <= L[j])
{
Insert(L, i, j);
break;
}
}
}
}
++++
===== - Wertetypen vs. Referenztypen =====
==== - Theorie ====
Alle Typen (int, strings, classes, int-array, ...) sind entweder Wertetypen (value types) oder Referenztypen (reference types).
Referenz- und Wertetypen unterscheiden sich darin, wo der Speicher für die Daten reserviert wird. Eine Variable, die einen **Wertetyp** repräsentiert, allokiert auf dem //Stack// den erforderlichen Speicher für die Daten. Der Stack ist im RAM angesiedelt, wird aber vom Prozessor durch einen sogenannten Stack Pointer direkt unterstützt. Dieser ist in der Lage, auf dem Stack neuen Speicher zu reservieren, kann ihn aber auch freigeben. Dieses Verfahren ist sehr effizient und schneller als das Allokieren von Speicher im //Heap// für **Referenztypen**. Als Heap wird der Speicher im RAM bezeichnet, der allgemeinen Zwecken zur Verfügung steht.
=== Wertetypen ===
**Wertetypen** sind z.B. int oder double. Man kann sagen, dass jede Variable, die einen Wertetypen repräsentiert, eine //eigene Kopie der Daten// hat. Dies veranschaulicht das folgende Beispiel:
int x = 3;
int y = x;
x = 42;
Console.WriteLine(x);
Console.WriteLine(y);
Wir deklarieren die Variable `x` von Type int und weisen ihr den Wert 3 zu. Dann erstellen wir eine neue int-Variable `y` und weisen ihr den gleichen Wert wie x hat zu. Ändern wir nun den Wert von x so bleibt der Wert von y unverändert, da `x` und `y` eigene Kopien ihrer Werte (deshalb: Wertetypen) haben!
=== Referenztypen ===
Anders sieht dies bei **Referenztypen** wie Klassen, String oder Arrays (aller Typen) aus:
int[] A = new int[] { 3, 7 };
int[] B = A;
A[1] = 42;
PrintArray(A); // note that this is a custom function!
PrintArray(B);
Da ein Array ein Referenztyp ist, ist `A` eine //Referenz//, welche auf den //Ort im Speicher zeigt//, wo die entsprechenden Daten abgelegt sind - daher der Name! In der zweiten Zeile wird deshalb nicht ein neues Array erstellt sondern einfach eine zweite Referenz (oder ein zweiter Zeiger) auf die gleichen Daten. Deshalb ist es auch nicht verwunderlich, dass die beiden PrintArray-Befehle das gleiche Resultat liefern. Möchte man wirklich ein neues Arrays erstellen, muss das Keyword `new` aufgerufen werden. Um die Werte vom einen Array in das andere zu kopieren, kann die `CopyTo()`-Funktion verwendet werden:
int[] A = new int[] { 3, 7 };
int[] B = new int[A.Length]; // allocates new memory in RAM
A.CopyTo(B, 0); // copies elements of A into B
A[1] = 42;
PrintArray(A);
PrintArray(B); // different output
==== - Referenztypen für Sortier-Algorithmen ====
Überlegungen zu Wertetypen vs. Referenztypen sind wichtig für Algorithmen wie unsere Sortieralgorithmen, die Arrays entgegennehmen. Sagen wir, du erzeugst ein neues int-Array und möchtest dieses sortieren: Soll das ursprüngliche Array sortiert werden, so dass das unsortierte Array nicht mehr zur Verfügung steht oder soll zuerst eine Kopie des unsortierten Arrays erstellt und erst dann sortiert werden?
=== Sortieren ohne Kopie ===
Soll das ursprüngliche Array sortiert werden, kann die Sortierfunktion vom Typ void sein (muss aber nicht). Es ist nicht nötig, dass die Funktion die sortierte Liste zurückgibt, da die ursprüngliche Liste gerade dort im Speicher sortiert wird, wo ihre Werte gespeichert sind:
public static void Selectionsort(int[] L)
{
// CODE TO SORT ARRAY HERE
// nothing to return
}
public static int[] Selectionsort2(int[] L)
{
// CODE TO SORT ARRAY HERE
return L;
}
public static void Main(string[] args)
{
int[] A = new int[] { 5, 3, 4, 1, 6, 2 };
PrintArray(A); // Output: { 5, 3, 4, 1, 6, 2 }
Selectionsort(A);
PrintArray(A); // Output: { 1, 2, 3, 4, 5, 6 }
}
=== Sortieren mit Kopie ===
Soll das ursprüngliche, unsortierte Array weiterhin zur Verfügung stehen, muss eine Kopie von diesem gemacht werden:
public static int[] Selectionsort(int[] L)
{
// create copy of array:
int[] K = new int[L.Length];
L.CopyTo(K, 0);
// CODE TO SORT ARRAY K (NOT L!) HERE
return K;
}
public static void Main(string[] args)
{
int[] A = new int[] { 5, 3, 4, 1, 6, 2 };
PrintArray(A); // Output: { 5, 3, 4, 1, 6, 2 }
int[] B = Selectionsort(A);
PrintArray(A); // Output: { 5, 3, 4, 1, 6, 2 }
PrintArray(B); // Output: { 1, 2, 3, 4, 5, 6 }
}
===== - Code Testing =====
==== - Theorie ====
=== Warum Code testen? ===
Die Idee vom **Programmieren mit Funktionen** ist, sich wiederholenden Code auf Funktionen auszulagern. Dadurch wird der Code übersichtlicher und kürzer und es gilt ‘aus den Augen, aus dem Sinn’: Funktionen die korrekt funktionieren, können immer wieder aufgerufen werden, ohne dass man sich wieder mit ihrem Code beschäftigen muss.
Essenziell dabei ist, dass diese Funktionen zu **100% korrekt funktionieren**!
Betrachten wir das Beispiel **Insertionsort**: Für den Insertionsort-Algorithmus haben wir die Helper-Funktion `Insert(...)` programmiert. Wenn unsere `Insertionsort(...)`-Funktion, in welcher die Insert-Funktion aufgerufen wird, nicht richtig funktioniert, müssen wir uns fragen, wo der Fehler liegt: In der Insert-Funktion oder im restlichen Code? Wenn wir die Insert-Funktion zuverlässig auf Herz und Nieren geprüft haben, können wir uns sicher sein, dass der Fehler im restlichen Code liegt. Damit finden wir den Fehler viel schneller, als wenn wir auch noch Insert überprüfen müssen.
Die Frage ist nun, wie wir Funktionen wie die Insert-Funktion zuverlässig testen können? Die Antwort lautet: **Unit Testing**
=== Unit Testing ===
Die Idee von **Unit Testing** oder **Modultests** ist: Teste deinen Code, in dem du Funktionen, Klassen usw. //alle einzeln ausführlich testest//. In unserem Projekt SortingAlgorithms würden wir also einzeln testen:
* Insert(int[] A)
* Insertionsort(int[] A)
* Bubblesort(int[] A)
* ...
Für grössere Softwares auch weitere Arten von Tests wie **Integration Tests** und **System Tests**, für uns sind aber Unit Tests ausreichend.
In C# und Visual Studio gibt es **professionelle Funktionalitäten für Unit Testing**, sind für unsere Ansprüche aber Overkill, weshalb wir unsere **eigenen Testfunktionen schreiben!**
=== Vorgehen beim Programmieren ===
Du möchtest einen Algorithmus in einer Funktion implementieren. Wie gehst du vor?
1. **Deklariere** die Funktion, z.B. `public static int[] Insert(int[] A, int i, int j)`. Sie soll //ausführbar// sein - hat die Funktion einen Rückgabetyp (ist also nicht void), so soll eine passende Grösse zurückgegeben werden (siehe Tipp unten),
1. Implementiere für die Funktion eine **Test-Funktion**, z.B. `public static void InsertTests()`.
1. Implementiere nun die **eigentliche Funktion**. Nutze die Test-Funktion zum Testen der Funktion. Die Test-Funktion soll also bei jedem Ausführen aufgerufen werden!
Beachte, dass du die Test-Funktion VOR der eigentlichen Funktion ausprogrammieren sollst!
//Tipp:// Gib am Anfang irgendetwas zurück - einfach damit der Code ausführbar ist.
public static int[] Selectionsort(int[] L)
{
// CODE FOR ALGORITHM HERE
return new int[] {2,3}; // return any int-array here
}
=== Was macht eine Test-Funktion? ===
Die Test-Funktion ruft die zu testende Funktion wiederholt für einige vorgegebenen Fälle auf und vergleicht die von der Funktion zurückgegebenen Resultate mit den vorgegebenen korrekten Resultate. Gibt die Funktion nichts zurück, sondern sortiert z.B. eine Liste, deren Referenz als Argument übergeben wird, so vergleicht man die sortierte Liste mit dem korrekten Resultat.
Zum Beispiel könnte man in `InsertTests()` den Aufruf `Insert(new int[] { 10, 11, 12, 13, 14, 15 }, 4, 2)` tätigen. Das von Insert zurückgegebene Array wird mit dem vorgegebenen, korrekten Resultat `new int[] { 10, 11, 14, 12, 13, 15 }` verglichen. Nun sollen zahlreiche weitere solche Vergleiche gemacht werden. Sind alle Vergleiche erfolgreich, so ist der Test erfolgreich und es wird eine entsprechende Nachricht ausgegeben.
Achte darauf, dass in der Test-Funktion **sämtliche Arten von Fälle** abgedeckt sind, also auch alle **speziellen Fälle**. Für InsertTests wären dies:
* Elemente mit Positionen mit Differenz 1: `Insert(...,5,4)`
* Element an Position 0 einfügen `Insert(...,4,0)`
* Korrekter Umgang mit falschen Eingaben, z.B. `Insert(...,2,5)`
Wird ein **Sortier-Algorithmus** getestet, wären solche //speziellen Fälle// relevant:
* Bereits sortiert: {0,1,2,3,4,5}
* Bereits sortiert bis auf 1 Element: {0,1,3,4,2,5}
* Worst case (genau umgekehrt sortiert): {5,4,3,2,1,0}
* Array mit nur 1 Element: {42}
* Array mit identischen Elementen: {3,1,3,3,2,4,1,3}
* Array mit lauter identischen Elementen: {3,3,3,3,3,3}
* ...
Natürlich sollen auch einige //normale Fälle// wie {3,6,2,5,1,4} getestet werden.
=== Tipp für C#-Arrays ===
Achtung: Zwei C#-Arrays `A1` und `A2` können nicht einfach verglichen werden: `if(A1 == A2) {...}`. Für einen solchen Vergleich benötigt es eine spezielle Vergleichsfunktion. Am besten programmierst du selbst eine:
public static bool ArraysAreEqual(int[] A1, int[] A2)
{
// compares arrays A1 and A2, returns true (false) if they are (not) equal
// Hint: Iterate through all elements and compare elements at same index. Arrays also must have same length.
}
==== - Auftrag 2 ====
Löse diesen Auftrag im SortingAlgorithm-Projekt.
=== Teil I ===
Schreibe für **Insert** eine **Test-Funktion**:
public static void InsertTests()
{
int failedCount = 0;
int succCount = 0;
// TESTS
...
// SUMMARY
// print summary: Were tests successful? If not, how many have failed?
...
}
Rufe die Test-Funktion innerhalb der Main-Methode auf:
public static void Main(string[] args)
{
InsertTests();
}
//Tipp:// Im Theorieblock oben findest du viele Tipps zu dieser Aufgabe.
++++Lösung|
public static void InsertTests()
{
int failedCount = 0;
int succCount = 0;
// REGULAR TESTS
if (ArraysAreEqual(Insert(new int[] { 10, 11, 12, 13, 14, 15 }, 4, 2), new int[] { 10, 11, 14, 12, 13, 15 })) { succCount++; } else { failedCount++; }
if (ArraysAreEqual(Insert(new int[] { 10, 11, 12, 13, 14, 15 }, 1, 0), new int[] { 11, 10, 12, 13, 14, 15 })) { succCount++; } else { failedCount++; }
if (ArraysAreEqual(Insert(new int[] { 10, 11, 12, 13, 14, 15 }, 5, 0), new int[] { 15, 10, 11, 12, 13, 14 })) { succCount++; } else { failedCount++; }
// TEST IF RAISES EXCEPTION WHEN IT SHOULD
try
{
Insert(new int[] { 10, 11, 12, 13, 14, 15 }, 1, 2);
failedCount++;
}
catch { succCount++; }
// SUMMARY
int nrTests = succCount + failedCount;
if (failedCount == 0)
{
Console.WriteLine("INSERT TEST SUCCESSFUL: " + succCount + "/" + nrTests + " successful.");
}
else
{
Console.WriteLine("INSERT TEST FAILED: " + failedCount + "/" + nrTests + " failed.");
}
}
++++
=== Teil II ===
Schreibe für die drei Sortieralgorithmen jeweils eine Test-Funktion: `BubblesortTests()`, `SelectionsortTests()`, `InsertionsortTests()`. Achte darauf, dass alle Spezialfälle (siehe Theorie oben) abgedeckt werden.
++++Lösung|
Beispielcode für Bubblesort. Für die anderen Sortieralgorithmen identisch, einfach //Bubblesort// durch andere Sortierfunktion ersetzen.
public static void BubblesortTests()
{
int countFailed = 0;
int countSucc = 0;
int[] A = new int[] { 1, 2, 3, 4, 5 };
Bubblesort(A);
if (ArraysAreEqual(A, new int[] { 1, 2, 3, 4, 5 })) { countSucc++; } else { countFailed++; }
int[] B = new int[] { 3, 5, 2, 4, 1 };
Bubblesort(B);
if (ArraysAreEqual(B, new int[] { 1, 2, 3, 4, 5 })) { countSucc++; } else { countFailed++; }
int[] C = new int[] { 5, 4, 3, 2, 1 };
Bubblesort(C);
if (ArraysAreEqual(C, new int[] { 1, 2, 3, 4, 5 })) { countSucc++; } else { countFailed++; }
int[] D = new int[] { 1, 3, 3, 2, 3 };
Bubblesort(D);
if (ArraysAreEqual(D, new int[] { 1, 2, 3, 3, 3 })) { countSucc++; } else { countFailed++; }
int[] E = new int[] { 5, 5, 5, 5, 3, 5, 5 };
Bubblesort(E);
if (ArraysAreEqual(E, new int[] { 3, 5, 5, 5, 5, 5, 5 })) { countSucc++; } else { countFailed++; }
// SUMMARY
int nrTests = countSucc + countFailed;
if (countFailed == 0)
{
Console.WriteLine("BUBBLESORT TEST SUCCESSFUL: " + countSucc + "/" + nrTests + " successful.");
}
else
{
Console.WriteLine("BUBBLESORT TEST FAILED: " + countFailed + "/" + nrTests + " failed.");
}
}
++++
===== - Delegates =====
Für die drei Sortieralgorithmen hast du oben drei eigene Test-Funktionen geschrieben. Diese Test-Funktionen sollten eigentlich identische sein, mit der Ausnahme der Aufrufe der Sortier-Funktionen. Es wäre doch schön, wenn man **nur eine Test-Funktion** `SortingTests(...)` schreiben könnte und als Argument die jeweilige Sortier-Funktion übergeben könnte:
SortingTests(Selectionsort);
SortingTests(Bubblesort);
SortingTests(Insertionsort);
Dies ist einfach umsetzbar mithilfe von sogenannten **Delegates**.
Ein **Delegate**, also ein **Delegierter**, ist jemand, der einen //Auftrag weiterleiten soll//. Beim Programmieren leitet ein Delegate //einen Funktionsaufruf weiter//. In Programmiersprachen spricht man dabei von einem **Function pointer / Funktionszeiger.**
Deklariere dazu parallel zu deinen Funktionen einen passenden Delegate:
public delegate void SortingAlgoDelegate(int[] L);
`SortingAlgoDelegate` kann nun stellvertretend für alle Funktionen verwendet werden, die ein int-Array entgegennehmen und ein solches zurückgeben.
Nun kann man die `SortingTests(...)`-Funktion entsprechend definieren:
public static void SortingTests(SortingAlgoDelegate sortingFunction)
{
// TESTS
// your tests here
// SUMMARY
// print a summary of tests: successful or failed? give details e.g. '4/5 tests failed'
}
Ruft man diese Funktion auf, muss man ihr nun eine passende Funktion übergeben.
==== - Auftrag 3 ====
Schreibe mithilfe von //Delegates// eine //einzige Testfunktion//, mit der sämtliche Sortieralgorithmen getestet werden können. Im Codebeispiel oben siehst du, wie die Grundstruktur dieser Funktion sein soll.
++++Lösung|
public static void SortingTests(SortingAlgoDelegate sortDel)
{
int failedCount = 0;
int succCount = 0;
// TESTS
// create list with jagged arrays: unsorted list and correctly sorted list
List TestList = new List();
TestList.Add(new int[][] { new int[] { 10, 11, 12, 13, 14, 15 }, new int[] { 10, 11, 12, 13, 14, 15 } });
TestList.Add(new int[][] { new int[] { 11, 13, 15, 10, 14, 12 }, new int[] { 10, 11, 12, 13, 14, 15 } });
TestList.Add(new int[][] { new int[] { 15, 14, 13, 12, 11, 10 }, new int[] { 10, 11, 12, 13, 14, 15 } });
TestList.Add(new int[][] { new int[] { 15, 14, 13, 12, 11, 10 }, new int[] { 10, 11, 12, 13, 14, 15 } });
TestList.Add(new int[][] { new int[] { 14, 11, 13, 10, 15, 12 }, new int[] { 10, 11, 12, 13, 14, 15 } });
TestList.Add(new int[][] { new int[] { 11, 11, 11, 10, 11, 11 }, new int[] { 10, 11, 11, 11, 11, 11 } });
foreach (var testPair in TestList)
{
int[] A = testPair[0];
int[] Asol = testPair[1];
sortDel(A);
if (ArraysAreEqual(A, Asol)) { succCount++; } else { failedCount++; }
}
// SUMMARY
int nrTests = succCount + failedCount;
if (failedCount == 0)
{
Console.WriteLine((sortDel.Method).ToString().ToUpper() + " TEST SUCCESSFUL: " + succCount + "/" + nrTests + " successful.");
}
else
{
Console.WriteLine((sortDel.Method).ToString().ToUpper() + " TEST FAILED: " + failedCount + "/" + nrTests + " failed.");
}
}
++++
===== - Rekursion =====
==== - Theorie ====
Die anspruchsvolleren Sortieralgorithmen basieren auf dem Prinzip der **Rekursion**. Deshalb macht es Sinn, sich zuerst kurz mit dieser zu beschäftigen.
Betrachte die **Fakultätsfunktion** aus der Mathematik:
$$n! = \text{faculty}(n) = n \cdot (n-1) \cdot \ldots \cdot 3 \cdot 2 \cdot 1$$
Zum Beispiel: $5! = 5\cdot 4\cdot 3\cdot 2\cdot 1 = 120$.
Es ist offensichtlich, dass in $5!$ auch $4!$, $3!$, $2!$ und $1!$ drin steckt:
$$5! = 5\cdot 4\cdot 3\cdot 2\cdot 1 = 5\cdot (4\cdot 3\cdot 2\cdot 1) = 5 \cdot 4!$$
Um $5!$ zu berechnen, muss man also zuerst $4!$ berechnen und für dieses benötigt man zuerst $3!$ usw.
Mit diesem Wissen kann man nun die Fakultätsfunktion //rekursiv// definieren:
$$n! = n \cdot (n-1)! \quad (\text{für } n > 1)$$
$$1! = 1$$
Beachte, dass die letzte Zeile benötigt wird, da sie uns sagt, wann die Rekursion abgebrochen werden soll.
==== - Auftrag 4 ====
Erstelle ein C#-Projekt //Recursion// und löse darin Aufgaben in diesem Kapitel.
Gehe dabei vor wie beschrieben in ...
=== Teil I: Fakultät ===
Ziel ist, die Fakultätsfunktion `Faculty(int n)` //rekursiv// in C# zu programmieren.
1. **Deklariere** die Funktion `Faculty(int n)` (aber noch nicht ausprogrammieren). Funktion soll //ausführbar// sein.
1. Implementiere für die Funktion eine **Test-Funktion** `public static void FacultyTests()`.
1. Implementiere nun die **eigentliche Funktion**. Nutze die Test-Funktion zum Testen der Funktion. Die Test-Funktion soll also bei jedem Ausführen aufgerufen werden!
++++Lösung|
++++
=== Teil II: Fibonacci ===
Mit Sicherheit kennst du die berühmte Fibonacci-Folge:
$$1,1,2,3,5,8,13,21,\ldots$$
Diese ist wie folgt rekursiv definiert:
$$a_n = a_{n-1} + a_{n-2} \quad (\text{für } n \geq 2)$$
$$a_0 = a_1 = 1$$
Implementiere die Funktion `fibonacci(int n)`, die einem das $n-$te Glied der Fibonaccifolge ausgibt, //rekursiv// in C#. Gehe vor wie gehabt: i) Deklaration, ii) Test-Funktion, iii) Implementieren & Testen
++++Lösung|
++++
===== - Anspruchsvolle (rekursive) Sortieralgorithmen =====
==== - Theorie ====
=== Quicksort ===
Quicksort ist ein rekursiver Sortieralgorithmus, der nach dem Prinzip //Teile und herrsche// arbeitet.
Zunächst wird die zu sortierende Liste in zwei Teillisten (linke und rechte Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Als Pivotelement kann man z.B. immer das letzte Element der Liste nehmen. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.
Anschliessend muss man also noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so weiter. Diese Selbstaufrufe werden als **Rekursion** bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekursion.
=== Mergesort ===
Wie beim Quicksort handelt es sich beim Mergesort um einen rekursiven, nach dem //Teile und herrsche//-Prinzip arbeitenden Sortieralgorithmus.
Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in zwei kleinere Listen, die jede für sich sortiert (rekursiv, wieder mit Mergesort) werden. Die kleinen sortierten Listen werden dann im Reissverschlussverfahren zu größeren sortierten Listen zusammengefügt (engl. (to) merge), bis eine sortierte Gesamtliste erreicht ist.
==== Auftrag 5 ====
Implementiere nun die beiden rekursiven Algorithmen. Füge dem Projekt aus Auftrag 1 die entsprechenden Funktionen hinzu.
=== Teil 1 ===
Implementiere den **Quicksort**-Algorithmus für //Listen//:
public static List Quicksort(List L)
{
// your code here
}
Natürlich sollst du, bevor du die Quicksort-Funktion programmierst, eine **Testfunktion** implementieren. Dazu kannst du zu einem grossen Teil die Testfunktion der vorherigen Sortierfunktionen verwenden, es benötigt aber kleine Anpassungen, da du hier mit Listen anstelle Arrays arbeitest.
Hier macht es Sinn, Listen anstelle von Arrays zu verwenden, weil man nicht weiss, wie viele Elemente die beiden Teillisten (kleiner und grösser als Pivot) enthalten. In einer weiteren Aufgabe schauen wir uns an, wie man den Quicksort //in-place// mit Arrays implementieren kann.
++++Lösung|
++++
=== Teil 2 ===
Implementiere zuerst eine **Merge**-Funktion. Diese nimmt zwei bereits sortierte Arrays `L1` und `L2` entgegen und führt diese zusammen (merged) in ein grosses, sortiertes Array (mit Länge `L1.Count + L2.count`).
public static int[] Merge(int[] L1, int[] L2)
{
// your code here
}
Implementiere dann die **Mergesort**-Funktion, in welcher due die Merge-Funktion von oben aufrufst:
public static int[] Mergesort(int[] L)
{
// your code here
}
++++Lösung|
++++
=== Teil 3 ===
Implementiere nun den **Quicksort**-Algorithmus **in-place** für //Arrays//:
public static void Quicksort(int[] L)
{
// your code here
}
In-place bedeutet, dass man immer mit dem ursprünglich gegebenen Array arbeitet und nur dessen Elemente //vertauscht//. Es werden also keine Teil-Arrays oder Listen erstellt.
Beachte, dass es kein Problem ist, zwei Funktionen mit //identischem Namen// zu haben, solange sie //unterschiedliche Argumente// verlangen, also z.B. `Quicksort(List L)` und `Quicksort(int[] L)`. Wird Quicksort aufgerufen `Quicksort(A)` entscheidet C# anhand des Datentyps von A (Liste oder Array?), welche der beiden Funktionen aufgerufen werden soll. Dies nennt man **Überladung von Funktionen/Methoden**.
++++Lösung|
++++
===== - Dynamische Programmierung =====
==== Aufgabe 1: Fibonacci nicht dynamisch ====
=== Teil I ===
In einer früheren Aufgabe hast du bereits die Glieder Fibonacci-Folge //rekursiv// berechnet. Öffne das entsprechende Projekt und bestimme, das höchste Folgenglied, welches du (resp. dein Computer) in vernünftiger Zeit berechnen kann.
++++Lösung|
MacBook Pro von sca: 42 (nice!)
++++
Wahrscheinlich ist diese Zahl deutlich kleiner als du erwartet hättest. Woran liegt es, dass diese Zahl so klein ist?
++++Lösung|
++++
=== Teil II ===
Erweitere deinen Code so um, dass dieser dir für die vorgegebene Zahl $n$ bestimmt, wie viele rekursive Funktionsaufrufe
Um `Fibonacci(3)` zu rekursiv zu bestimmen, wird insgesamt $5\times$ die Funktion `Fibonacci(i)` aufgerufen:
`Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = (Fibonacci(1) + Fibonacci(0)) + Fibonacci(1)`
++++Tipps|
Definiere einen Counter als eine Art globale Variable, also eine Variable, die //ausserhalb// der Main-Methode definiert wird. Jedesmal, wenn die Fibonacci-Funktion aufgerufen wird, kann dann dieser Counter um 1 erhöht werden.
++++
Bestimme für alle Werte $n$ von $1$ bis zum maximalen Wert, wie viele Funktionsaufrufe es jeweils gibt. Wie genau entwickelt sich diese Anzahl Funktionsaufrufe mit steigendem $n$?
++++Lösung|
public static long fibonacciCounter = 0;
public static int FibonacciWithCounter(int n)
{
fibonacciCounter++;
if (n <= 1) { return 1; }
return FibonacciWithCounter(n - 1) + FibonacciWithCounter(n - 2);
}
public static long[] FibonacciWithCounterWrapper(int n)
{
fibonacciCounter = 0;
int fib = FibonacciWithCounter(n);
return new long[] { (long)fib, fibonacciCounter };
}
public static void Main(string[] args)
{
List fibonacciCountList = new List();
for (int n = 0; n < 30; n++)
{
long[] result = FibonacciWithCounterWrapper(n);
fibonacciCountList.Add(result[1]);
Console.WriteLine("n = " + n + ", count: " + result[1]);
}
for (int i = 0; i < fibonacciCountList.Count-1; i++)
{
Console.WriteLine((double)fibonacciCountList[i + 1] / fibonacciCountList[i]);
}
}
Findet, dass Verhältnis von $\frac{a_{n+1}}{a_n}$ immer etwa 1.6 ist. D.h. **exponentielles Wachstum**.
++++
=== Teil 3 ===
Erkläre nun genau, warum diese maximale Folgenglied so tief ist. Wo genau liegt das Problem? Hast du Ideen, wie man dieses umgehen könnte?
++++Lösung|
Siehe //Theorie// in der nächsten Aufgabe.
++++
==== Aufgabe 2: Fibonacci dynamisch ====
++++Theorie|
Das Problem im Code der vorherigen Aufgabe ist, dass die Anzahl Funktionsaufrufe exponentiell steigt. Dadurch ist die Anzahl rekursiver Funktionsaufrufe bereits für Zahlen wie $n=42$ sehr hoch (und zwar $433'494'437$). Dies liegt daran, dass die Fibonacci-Funktion immer wieder für die gleiche Zahl aufgerufen wird. Zum Beispiel wird in der Berechnung für `Fibonacci(42)` insgesamt $102'334'155$ `Fibonacci(3)` berechnet. Das ist nicht sehr effizient!
Lösung: Verhindere, dass die ein Folgenglied mehrfach berechnet wird. Dazu müssen die bereits berechneten Folgenglieder in einer Liste gespeichert werden. Anstelle, dass ein Folgenglied erneut berechnet wird, liest man den Wert aus der Liste aus.
Diese Art der Programmierung wird **dynamische Programmierung** genannt. Das Speichern der Zwischenresultate wird **Memoisation** genannt.
++++
=== Teil I ===
Implementiere nun die rekursive Fibonacci Funktion dynamisch. Das heisst, die Zwischenresultate sollen in einer Liste oder einem Array gespeichert und wieder verwendet werden (Memoisation). Wie weit kannst du nun Folgenglieder der Fibonacci-Folge berechnen?
=== Teil II ===
Bestimme nun wieder, wie viele rekursive Funktionsaufrufe nötig sind. Vergleiche die dynamische mit der vorherigen, nicht dynamischen Implementierung.
++++Lösung|
Anzahl rekursive Funktionsaufrufe ist nun **linear** in $n$, genauer: $2n - 1$. Für $n=42$ sind es damit $83$ (dynamisch). Stellt man es den über 400 Millionen Funktionsaufrufe vom nicht dynamischen Code gegenüber, so sieht man, dass dies eine enorme Steigerung der Effizient ist!
++++