Sortieralgorithmen & Rekursion in C#

In diesem Kapitel werden einige bekannte Sortieralgorithmen kurz beschrieben.

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 …

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.

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.

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.
2. Wende den Algorithmus auf Papier auf eine kurze Beispielliste an.
3. Implementiere den Algorithmus.

Implementiere den Selectionssort-Algorithmus.

Implementiere den Bubblesort-Algorithmus.

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.
2. Implementiere den Insertionsort-Algorithmus. Verwende dazu die oben implementierte Insert-Funktion.

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 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!

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

Ü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?

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 }
}

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 }
}

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

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!

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),
2. Implementiere für die Funktion eine Test-Funktion, z.B. public static void InsertTests().
3. 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 
}

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.

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.
}

Löse diesen Auftrag im SortingAlgorithm-Projekt.

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.

Schreibe für die drei Sortieralgorithmen jeweils eine Test-Funktion: BubblesortTests(), SelectionsortTests(), InsertionsortTests(). Achte darauf, dass alle Spezialfälle (siehe Theorie oben) abgedeckt werden.

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.

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.

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.

Erstelle ein C#-Projekt Recursion und löse darin Aufgaben in diesem Kapitel. Gehe dabei vor wie beschrieben in …

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.
2. Implementiere für die Funktion eine Test-Funktion public static void FacultyTests().
3. Implementiere nun die eigentliche Funktion. Nutze die Test-Funktion zum Testen der Funktion. Die Test-Funktion soll also bei jedem Ausführen aufgerufen werden!

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

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.

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.

Implementiere nun die beiden rekursiven Algorithmen. Füge dem Projekt aus Auftrag 1 die entsprechenden Funktionen hinzu.

Implementiere den Quicksort-Algorithmus für Listen:

public static List<int> Quicksort(List<int> 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.

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
}

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<int> 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.

In einer früheren Aufgabe hast du bereits die Fakultät rekursiv berechnet. Öffne das entsprechende Projekt und berechne:

Berechne mit dieser Funktion die Fakultät für folgende Werte: 12,13,

http://www.wackerart.de/mathematik/big_numbers/factorial_table.html