{ "cells": [ { "cell_type": "markdown", "id": "8a4e0d89-d0e0-4050-bd14-4a8099b19943", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "ed3d8272-632e-4353-ba3d-0e94a017a9c7", "metadata": {}, "source": [ "# Sortieralgorithmen" ] }, { "cell_type": "markdown", "id": "e82f33c2-ae65-4a73-8339-64d43ac13178", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "a7d684cd-4ba6-4455-8acf-cb53901f6cf5", "metadata": {}, "source": [ "
\n", "Ziel des Notebooks:\n", "\n", "- Anwendungsbereiche von Sortieralgorithmen verstehen\n", "- Exemplarisch Sortieralgorithmen verstehen und anwenden lernen\n", "- Vor- und Nachteile verschiedener Sortieralgorithmen verstehen\n", "\n", "
\n", " \n", "Mathematische Tools:\n", "- Kombinatorik\n", "- Landau Notation und Grenzwertverhalten\n", "
" ] }, { "cell_type": "markdown", "id": "d5a0231a-98e7-499c-8c38-0d905d86de10", "metadata": { "tags": [] }, "source": [ "***" ] }, { "cell_type": "code", "execution_count": null, "id": "2c2c5afb-a0bb-4e30-b4e3-205fb9b592a8", "metadata": { "tags": [] }, "outputs": [], "source": [ "using Random" ] }, { "cell_type": "markdown", "id": "94a57d2e-5078-4972-8f3c-a049b42305d8", "metadata": {}, "source": [ "Man kennt es: Die letzte Klausur wird auf den fertig korrigiert Stapel gelegt und nun muss man nur noch die 30 Klausuren irgendwie in eine sinnvolle Reihenfolge bringen ...
\n", "Nachdem man sich auf eine sinnvolle Sortierung, wie etwa die Anfangsbuchstaben der Vornamen, geeinigt hat, stellt sich die Frage, wie man effizient sortieren kann. Dieses Problem spielt nicht nur im Alltag, sondern insbesondere in der Informatik eine sehr große Rolle.
\n", "Tatsächlich ist es uns meistens nicht so bewusst, aber wir sind in der heutigen Zeit enorm auf die Effizienz von Sortieralgorithmen angewiesen, um etwa beim Online Shoppen unter den tausenden Angeboten das Günstigste zu finden oder aber bei der Literaturrecherche nach der Spieltheorie bei den Aborigines zu suchen." ] }, { "cell_type": "markdown", "id": "4015c592-9c41-48d8-b4a1-ffd872c16b04", "metadata": {}, "source": [ "Um für diese Klasse von Problemen Lösungen zu finden werden schon seit den 1950er Jahren Sortieralgorithmen entwickelt. Also Algorithmen, die Listen oder ähnliche Datenstrukturen in eine gewünschte Ordnung bringen. Dabei ist die Forschung noch immer im Gange und es werden stets neue Algorithmen entworfen, wie Timsort in 2002, welche große Anwendung finden." ] }, { "cell_type": "markdown", "id": "a19c87b9-8f9f-42e6-ae9a-ee591e600d83", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "5f0045c3-3a81-40be-bcd4-a0214fbdfaf4", "metadata": {}, "source": [ "Damit wir aber überhaupt über Sortierung sprechen können, muss man eine Möglichkeit finden, gegebene Elemente zu vergleichen und sich insbesondere festlegen, wie man diese vergleichen möchte. Diese Möglichkeit geben uns Ordnungsrelationen, bzw., für unsere Zwecke, totale Ordnungen.\n", "\n", "Totale Ordnungen sind wie folgt definiert:\n", "
\n", " Definition totale Ordnung
\n", " Eine Relation $\\leq$ auf einer Menge $M$ wird totale Ordnung gennant, wenn für alle $x,y \\in M$ die folgenden Bedingungen gelten:
\n", " 1. $x \\leq x$ (Reflexivität)
\n", " 2. $x \\leq y \\wedge y \\leq x \\implies x = y$ (Antisymmetrie)
\n", " 3. $x \\leq y \\wedge y \\leq z \\implies x \\leq z$ (Transitivität)
\n", " 4. $x \\leq y \\vee y \\leq x$ (Totalität)
\n", "
" ] }, { "cell_type": "markdown", "id": "dfe7cb99-98c0-4ea4-a64f-bbb53bba84fd", "metadata": {}, "source": [ "Das Konzept von Ordnungsrelationen begegnet uns dabei ziemlich häufig im Alltag, das wohl wichtigste Merkmal einer totalen Ordnung ist hierbei die vierte Bedingung. Totalität besagt, dass alle Elemente der Menge miteinander vergleichbar sein müssen. Hierbei ist das $\\leq$ nur ein Platzhalter für eine Relation und bedeutet nicht notwendigerweise das $\\leq$ wie wir es etwa auf den reellen Zahlen $\\mathbb{R}$ kennen, was auch in folgender Aufgabe deutlich wird:" ] }, { "cell_type": "markdown", "id": "98fd0476-8d5e-45a2-b933-48c0570ca9ef", "metadata": {}, "source": [ "
\n", "\n", "### Aufgabe\n", "***\n", "Handelt es sich bei der Relation (nicht-echte) Teilmenge auf der Potenzmenge der ganzen Zahlen ($\\mathcal{P} (\\mathbb{Z})$) um eine totale Ordnung?\n", "\n", "Erinnerung:
\n", "$\\mathcal{P}(\\mathbb{Z}) = \\{ A \\mid A \\subseteq \\mathbb{Z}\\}$ und $ A \\subseteq B \\iff \\forall x \\in A: x \\in B$\n", "\n", "Fallen Ihnen im \"echten\" Leben Mengen ein auf denen eine (totale) Ordnung besteht, etwa Namen, Kleidungsgrößen oder Maße von z.B. Büchern? Wenn ja, wieso besteht auf ihnen eine totale Ordnung oder wieso nicht?\n", "
" ] }, { "cell_type": "markdown", "id": "c9eac971-1816-45ae-8ec6-b5d88b1c26f2", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "0a0c1454-9f76-4f36-89e3-88b21cc90eb2", "metadata": {}, "source": [ "### Sortieralgorithmen" ] }, { "cell_type": "markdown", "id": "6c1b7430-b6a5-46bd-8da9-b62a0ea85a0c", "metadata": {}, "source": [ "Nun wollen wir uns allerdings wieder dem Sortieren und damit den Sortieralgorithmen widmen. Wir werden nun exemplarisch zwei bzw. drei Sortieralgorithmen kennenlernen. Keine Sorge, falls Sie bisher nicht viel Programmiererfahrung haben. Es wird kein Programmieren notwendig sein und zusätzlich zu den folgenden Erklärungen der Algorithmen gibt es viele weitere Ressourcen im Internet, die Sortieralgorithmen anschaulich erklären." ] }, { "cell_type": "markdown", "id": "b56ec98d-6302-45e0-97e0-f8fb9533717b", "metadata": {}, "source": [ "Ein etwas langsamer Sortieralgorithmus, der dafür durch seine Einfachheit überzeugen kann, ist **Selectionsort**:" ] }, { "cell_type": "markdown", "id": "bc52aa6e-f3bb-4735-8fa4-d8b68fc26afd", "metadata": {}, "source": [ "Die Idee von **Selectionsort** ist es, das kleinste Element der Liste zu finden und dann an die erste Stelle zu tauschen. Dies wiederholt man mit der restlichen Liste so oft, bis die Liste nur noch aus einem Element besteht.
\n", "In einfachem Pseudocode könnte der Algorithmus wie folgt formuliert werden:
\n", "\n", "
\n", "Pseudocode von Selectionsort \n", " \n", "Der Input ist hierbei eine Liste und eine gegebene Ordnung\n", "1. Wähle das erste Element der Liste als aktuelles Minimum.\n", "2. Durchlaufe den Rest der Liste und setze das aktuelle Minimum neu, falls ein kleineres Element gefunden wird.\n", "3. Wenn das Ende der Liste erreicht ist, tausche das gefundene kleinste Element mit der ersten Stelle der Liste.\n", "4. Setze den Start der Liste bei dem Element nach dem soeben an den Anfang getauschten und wiederhole ab da die Schritte 1. bis 4..
\n", "Falls die so entstandene Teilliste nur ein Element enthält, so ist die Liste fertig sortiert.
\n", "
\n", "\n", "Wir werden im Folgenden erstmal die natürlichen Zahlen und die Ordnung \"$\\leq$\" verwenden, falls nicht anders spezifiziert." ] }, { "cell_type": "markdown", "id": "d7c50fe9-5439-4c35-aad4-0dd733249c9b", "metadata": {}, "source": [ "So könnte eine Implementierung des Algorithmus in Julia aussehen:" ] }, { "cell_type": "code", "execution_count": null, "id": "6ca3f27f-6a7c-4b01-9d7b-59e82f5cba9d", "metadata": { "tags": [] }, "outputs": [], "source": [ "function selectionsort(A)\n", " n = length(A)\n", " for i=1:n # Durchlaufe die Liste (äußere Schleife)\n", " min = i; # Wähle das erste Element der Liste als aktuelles Minimum\n", " for j=i:n # Durchlaufe die Teilliste beginnend bei i um dort das kleinste Element zu finden (innere Schleife)\n", " if A[j] < A[min] # Teste ob das aktuelle Element kleiner als das bisherige Minimum ist\n", " min = j; # Falls das aktuelle Elemnet kleiner als das bisherige Minimum ist, update das Minimum\n", " end\n", " end\n", " println(\"Tauschen von \" * string(A[i]) * \" und \" * string(A[min])) # Ausgabe\n", "\n", " tmp = A[i]; # Tausche erstes Element von Teilliste und kleinstes gefundenes Element in Teilliste\n", " A[i] = A[min];\n", " A[min] = tmp;\n", "\n", " println(A) # Ausgabe der Liste\n", " println()\n", " end\n", " println(\"Sortierte Liste:\")\n", " println(A)\n", " return\n", "end" ] }, { "cell_type": "code", "execution_count": null, "id": "faeb5940-0e62-492b-b11b-cd563cd8c6a7", "metadata": {}, "outputs": [], "source": [ "n = 10; # Länge der zu sortierenden Liste\n", "m = 100; # Maximaler (möglicher) Wert der zu sortierenden Liste\n", "\n", "A = rand(1:m, (n)); # 1:m gibt die Spanne der zu sortierenden Liste an; \n", " # \"(n)\" sagt Julia, dass es sich um einen Vektor (für unsere Zwecke ausreichend gute \"Liste\") handelt.\n", "\n", " # rand generiert uns mit den Informationen, die wir der Funktion liefern eine zufällige Liste \n", " # (in diesem Fall Vektor) mit Zahlen zwischen 1 und m\n", "\n", "println(\"Unsortierte (zufällige) Liste:\")\n", "println(A) # Ausgabe der zufälligen Liste vor Sortierung\n", "println()\n", "\n", "A = selectionsort(A)" ] }, { "cell_type": "markdown", "id": "110816c6-aacd-494c-911e-f372e893187d", "metadata": {}, "source": [ "Probieren Sie den Algorithmus doch mal aus (in dem Sie die Zelle direkt hierüber ausführen mit STRG + Enter) - es werden jedesmal neue zufällige Listen generiert und der Zustand der Liste nach jedem interessanten Schritt (Tauschen von Elementen und Finden eines neuen aktuellen Minimums) ausgegeben." ] }, { "cell_type": "markdown", "id": "9e693fb3-23df-4074-a662-399803efd8a6", "metadata": {}, "source": [ "Für das bessere Verständnis des Algorithmus kann es hilfreich sein, den Algorithmus Schritt für Schritt durchzugehen und zu überlegen, was die einzelnen Schritte bewirken und sich dies ggf. aufzumalen. Insbesondere bei diesem (noch) relativ simplen Sortieralgorithmus lohnt sich dies, da der nachfolgende Algorithmus dies vermutlich nicht mehr zulässt." ] }, { "cell_type": "markdown", "id": "767c0f58-41f4-462d-9600-b3a8f65ea411", "metadata": { "tags": [] }, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Sortieren Sie die folgende Liste handschriftlich oder hier im Notebook mit Hilfe von **Selectionsort** und notieren sie dabei alle interesssanten Zwischenschritte
(Tauschen von Elementen und finden eines neuen aktuellen Minimums, vgl. Ausgabe von Algorithmus oben; es muss nicht aufgeschrieben werden, welche Elemente getauscht wurden/werden):\n", " \n", "[3, 5, 7, 10, 16, 3, 5, 6, 8, 2]\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "2df5889c-05f6-4db2-a240-3d2d8c58fa46", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "038642dd-cfa6-47d4-84f8-daad3a3875b2", "metadata": {}, "source": [ "Im Gegensatz dazu ist **Mergesort** ein etwas elaborierterer, aber auch schnellerer Algorithmus, welchen wir nun auch noch betrachten wollen:" ] }, { "cell_type": "markdown", "id": "95de0d24-2da5-46da-a5ce-1543ea7d57c8", "metadata": {}, "source": [ "Die Idee von **Mergesort** ist es mit Hilfe von Rekursion die zu sortierende Liste immer weiter in kleinere Teillisten aufzuteilen, sodass Listen aus einzelnen Elementen übrig bleiben, welche dann zusammengefügt werden und dabei sortiert werden. Dieses Konzept vom Aufteilen eines Problems in viele kleinere Teilproblemen, welche einfacher zu lösen sind, wird auch Divide & Conquer genannt.
\n", "In einfachem Pseudocode könnte der Algorithmus wie folgt formuliert werden:\n", "\n", "
\n", "Pseudocode von Mergesort \n", " \n", "Der Input ist hierbei eine Liste und eine gegebene Ordnung\n", "1. Zerlege die unsortierte Liste in der Mitte in zwei etwa gleich große Teillisten.\n", "2. Sortiere jede Teilliste rekursiv, indem man auf den Teillisten Mergesort aufruft, bis jede Teilliste nur noch ein Element enthält, da sie dann als sortiert gelten.\n", "3. Füge die sortierten Teillisten zusammen (hierbei ist die Sortierung einzuhalten)\n", "<\\div>\n", "\n", "Hierbei ist zu beachten, dass das letzte Zusammenfügen der sortierten Teillisten sehr einfach ist, da die Teillisten bereits sortiert sind.\n", "Außerdem gibt es verschiedene Arten diesen Algorithmus zu implementieren - also tatsächlich umzusetzen. Eine Unterscheidungsmöglichkeit sind \"rekursive\" oder \"iterative\" Programmierung. Dazu finden sich viele anschauliche Ressourcen online, dies würde allerdings diesen Rahmen sprengen." ] }, { "cell_type": "markdown", "id": "69e03af7-a311-442a-a706-fe9175812a9d", "metadata": {}, "source": [ "Es folgt nun eine mögliche iterative Implementierung von Mergesort in Julia mit zufälligen Listen und der Ausgabe vom Zustand der Liste nach jedem interessanten Schritt (nach jedem Zusammenfügen von Teillisten). Fühlen Sie sich nicht erschlagen von dem folgenden Code, das Verstehen dieses ist nicht notwendig, lediglich die obige Idee vom Mergesort Algorithmus." ] }, { "cell_type": "code", "execution_count": null, "id": "064988db-a48b-43ae-966c-fe40b2322bf6", "metadata": { "tags": [] }, "outputs": [], "source": [ "function mergesort(A)\n", " n = length(A);\n", " \n", " curr_size = 1; # Länge der Teillisten\n", " \n", " while(curr_size <= n-1) # Durchlaufe die Liste so oft, bis die Teillisten länger als die Hälfte der Liste sind\n", " if curr_size * 2 < n # Ausgabe\n", " println(\"Sortiere \" * string(curr_size * 2) * \"er Paare\");\n", " else\n", " println(\"Sortiere \" * string(n) * \"er Paare\");\n", " end\n", " \n", " left_start = 1 # Startpunkt der aktuellen Teilliste\n", " while(left_start <= n-1) # Durchlaufe die Liste solange, bis der Startpunkte am Ende der Liste angekommen ist\n", " if left_start + curr_size > n # Spezialfall, wenn Liste sich nicht perfekt in Teillisten aufteilen lässt\n", " left_start = left_start + 2 * curr_size\n", " continue\n", " end\n", " if left_start + 2 * curr_size - 1 > n # Spezialfall, wenn Liste sich nicht perfekt in Teillisten aufteilen lässt\n", " A[left_start: n] = merge_concat(A[left_start:left_start + curr_size - 1], A[left_start + curr_size: n]);\n", " else\n", " # Normalfall: Merge Teillisten, die bereits sortiert sind zusammen\n", " A[left_start:left_start + 2 * curr_size-1] = merge_concat(A[left_start:left_start + curr_size - 1], A[left_start + curr_size: left_start + 2 * curr_size-1])\n", " end\n", " \n", " left_start = left_start + 2 * curr_size; # Setze Startpunkt der aktuellen Teilliste weiter \n", " println(A); # Ausgabe\n", " end\n", " \n", " println()\n", " curr_size = curr_size * 2; # Erhöhe Länge der aktuellen Teillisten\n", " end\n", " println(\"Sortierte Liste:\")\n", " println(A)\n", " return\n", "end\n", "\n", "function merge_concat(A,B)\n", " C = Array{Int64}(undef, (length(A) + length(B)))\n", " \n", " i = 1; # Counter für aktuell betrachtetes Element in Liste A\n", " j = 1; # Counter für aktuell betrachtetes Element in Liste B\n", " \n", " while(i < length(A) + 1 || j < length(B) + 1) # Durchlaufe die beiden Listen so lange, bis die Enden beider Listen erreicht sind\n", " if((i < length(A) + 1) && (j == length(B) + 1 || A[i] <= B[j])) # Fall, dass das aktuelle Element in A kleiner als in B ist\n", " C[i+j-1] = A[i];\n", " i = i+1;\n", " end\n", " \n", " if((j < length(B) + 1) && (i == length(A) + 1 || A[i] > B[j])) # Fall, dass das aktuelle Element in B kleiner als in A ist\n", " C[i+j-1] = B[j];\n", " j = j+1;\n", " end\n", " end\n", " return C\n", "end" ] }, { "cell_type": "code", "execution_count": null, "id": "dd5c4cf7-2449-4219-91c3-ed9af07fa5a6", "metadata": {}, "outputs": [], "source": [ "n = 10 # Länge der zu sortierenden Liste\n", "m = 100 # Maximaler (möglicher) Wert der zu sortierenden Liste\n", "\n", "A = rand(1:m, (n)); # 1:m gibt die Spanne der zu sortierenden Liste an; \n", " # \"(n)\" sagt Julia, dass es sich um einen Vektor (für unsere Zwecke ausreichend gute \"Liste\") handelt.\n", "\n", " # rand generiert uns mit den Informationen, die wir der Funktion liefern eine zufällige Liste \n", " # (in diesem Fall Vektor) mit Zahlen zwischen 1 und m\n", "\n", "println(\"Unsortierte (zufällige) Liste:\")\n", "println(A) # Ausgabe der zufälligen Liste vor Sortierung\n", "println()\n", "\n", "A = mergesort(A);" ] }, { "cell_type": "markdown", "id": "ccfbd70a-b726-44ca-835c-a4a9c671a9a3", "metadata": {}, "source": [ "Auch diesen Algorithmus können Sie mit zufällig generierten Listen ausprobieren, indem Sie die Zelle direkt hierüber mit STRG + Enter ausführen." ] }, { "cell_type": "markdown", "id": "9aeb7a3c-e7f7-46d3-aae9-c23174824bdf", "metadata": { "tags": [] }, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Sortieren Sie die folgende Liste handschriftlich oder hier im Notebook mit Hilfe von **Mergesort** und notieren sie dabei alle interesssanten Zwischenschritte
(..., vgl. Ausgabe von Algorithmus oben):\n", " \n", "(Verwenden Sie hierbei die Ordnung Rot $\\leq$ Grün $\\leq$ Blau $\\leq$ Gelb)\n", " \n", "[Rot, Gelb, Grün, Blau, Grün, Gelb, Rot, Rot]\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "55d1ac1e-8cdd-4a31-a75c-a5338e84e970", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "d18c35dc-5f57-4f19-8f7e-dd22d115542b", "metadata": {}, "source": [ "Nun sollen Sie selber nach einem Sortieralgorithmus recherchieren, diesen verstehen und anwenden lernen. Dabei schließen wir nur die beiden obigen und Insertion Sort aus, da wir diesen Algorithmus im Folgenden noch betrachten werden." ] }, { "cell_type": "markdown", "id": "9b41d813-8ecf-4609-bfe8-781258676ffc", "metadata": {}, "source": [ "
\n", " \n", "### Recherche-Aufgabe\n", "***\n", "Suchen Sie (z.B. im Internet) nach Sortieralgorithmen und wählen Sie sich einen interessanten (nicht Selection-, Merge- oder Insertionsort) aus. Verstehen Sie diesen Algorithmus und erklären Sie die Idee des Algorithmus. Es ist nicht notwendig Code zu schreiben. Wenden Sie den Sortieralgorithmus mit der üblichen kleiner gleich Relation auf folgende Liste an und notieren sie dabei die Liste nach jedem interessanten Schritt (mindestens nach jedem Tausch):\n", " \n", "[ 5, 6, 8, 9, 1, 2, 4, 7, 3, 10 ]\n", " \n", "Mögliche zu betrachtende Algorithmen mit Schwierigkeitsgraden zur Orientierung sind:\n", "1. Bubblesort, eher einfach\n", "2. Quicksort, etwas schwieriger\n", "3. Heapsort, schwierig\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "a64f1d83-39f7-4fc7-8a20-c8b18a721430", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "7e37873e-ebab-4e13-870c-06ee70ad20d5", "metadata": {}, "source": [ "### Laufzeiten von Sortieralgorithmen und Landau Notation\n" ] }, { "cell_type": "markdown", "id": "d53c77f7-ae14-412d-8a66-2f907d9d5503", "metadata": {}, "source": [ "Die Laufzeitanalyse von Sortieralgorithmen befasst sich mit der Bestimmung der Zeitkomplexität von Sortieralgorithmen. Das Ziel ist es zu verstehen, wie sich die Laufzeit, also die Zeit, die ein Algorithmus braucht um eine Aufgabe zu erledigen, mit der Größe der Eingabe ändert.\n", "\n", "Die asymptotische Laufzeitanalyse ist eine Methode, die in der Informatik weit verbreitet ist, um die Laufzeit von Algorithmen zu analysieren. Dabei wird versucht, die benötigten Operationen eines Algorithmus, wie etwa im Fall von Sortieralgorithmen, das Vergleichen von Elementen oder das Tauschen von Elementen, zu zählen und so in Abhängigkeit der Größe der Eingabe eine Funktion für die obere Grenze der benötigten Operationen zu formulieren.\n", "\n", "Die asymptotische Laufzeitanalyse klassifiziert diese (Laufzeit-)Funktion dann in eine von mehreren Klassen, die auf der Wachstumsgeschwindigkeit der Funktion basieren. Die häufigsten Klassen sind $\\mathcal{O}(1)$, $\\mathcal{O}(\\log(n))$, $\\mathcal{O}(n)$, $\\mathcal{O}(n \\cdot \\log(n))$, $\\mathcal{O}(n^2)$ und $\\mathcal{O}(2^n)$. Die O-Notation gibt dabei an, wie schnell die Laufzeit des Algorithmus im schlimmsten Fall mit der Größe der Eingabe wächst.\n", "\n", "Um dies besser zu verstehen schauen wir uns aber zunächst eine (für unsere Zwecke hinreichende) Definition von O-Notation, bzw. Landau-Notation, genauer an:" ] }, { "cell_type": "markdown", "id": "605b1e32-91c3-4a76-84fe-b677a761a4c0", "metadata": {}, "source": [ "
\n", " Definition Landau-Notation
\n", " Sei $f, g:\\mathbb{R} \\to \\mathbb{R}$ zwei Funktionen. Wir sagen, dass $f \\in \\mathcal{O}(g)$, wenn:
\n", " $$\n", " \\exists C > 0: \\exists x_0 \\in \\mathbb{R}: \\forall x \\geq x_0: f(x) \\leq C \\cdot g(x)\n", " $$\n", "
\n", "

" ] }, { "cell_type": "markdown", "id": "dba9cacc-5992-4159-a512-30784ea9d52d", "metadata": {}, "source": [ "Leider gibt es einige verschiedene (teils sich gegenseitig widersprechende) Möglichkeiten Landau Notation zu verwenden und zu definieren. Wir werden hier $f \\in \\mathcal{O}(g)$, wie oben, verwenden, allerdings gibt es auch die - mathematisch, syntaktisch etwas verwirrende Schreibweise - $f = \\mathcal{O}(g)$ für das gleiche.

" ] }, { "cell_type": "markdown", "id": "0e9d25a2-6a9f-4bf0-b92b-e3eee40db08f", "metadata": {}, "source": [ "Es gibt nicht nur das $\\mathcal{O}$ Symbol für obere Schranken von Funktionen, sondern auch $\\Omega$ für untere Schranken und weitere Klassifizierungen, allerdings interessieren wir uns für unsere Zwecke nur für die oberen Schranken der benötigten Operationen für die Sortieralgorithmen. Weiterhin interessieren wir uns natürlich für möglichst \"langsam wachsende\" Funktionen $g$, also möglichst niedrige obere Schranken." ] }, { "cell_type": "markdown", "id": "c9c0ce84-3d7f-4451-a774-aebf2d1535fb", "metadata": {}, "source": [ "Zunächst aber erstmal eine kleine Verständnisaufgabe:\n", "\n", "\n", "
\n", " \n", "### Aufgabe\n", "***\n", "Zeige, dass für $f,g:\\mathbb{R} \\to \\mathbb{R}, \\hspace{0,2cm} f(x) = x+100, \\hspace{0,2cm} g(x) = x^2$, gilt, dass $f \\in \\mathcal{O}(g)$.\n", " \n", "Hinweis: Eine Möglichkeit ist es die Ableitungen der beiden Polynome zu untersuchen und zu zeigen, dass die Ableitung der einen Funktion (schneller) wächst als die andere, um dann mit passendem $C$ und $x_0$ zu zeigen, dass $f(x) \\leq C \\cdot g(x)$ für $x \\geq x_0$.\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "de05dadf-ce34-4f23-bf8c-03db12c780a7", "metadata": {}, "source": [ "Weil die Laufzeitanalyse allerdings im Allgemeinen etwas komplex ist und eigentlich ein eigenes Notebook erfordern würde, wollen wir uns als letztes noch einmal einen weiteren Sortieralgorithmus anschauen und dessen Laufzeit analysieren." ] }, { "cell_type": "markdown", "id": "d026bc35-b8fe-4298-96c7-ebf09412a78c", "metadata": {}, "source": [ "Der folgende Sortieralgorithmus wird Insertionsort genannt und hat folgende Idee:" ] }, { "cell_type": "markdown", "id": "a6a07b9e-cd67-4c86-bde5-c6bbcc4e94b0", "metadata": {}, "source": [ "Die Idee von **Insertionsort** ist es, am Anfang der Liste eine sortierte Liste aufzubauen und Stück für Stück die nachfolgenden Listenelemente in den sortierten Anfang an die passende Stelle einzufügen.
\n", "In einfachem Pseudocode könnte der Algorithmus wie folgt formuliert werden:
\n", "\n", "
\n", "Pseudocode von Selectionsort \n", " \n", "Der Input ist hierbei eine Liste und eine gegebene Ordnung\n", "1. Betrachte das erste Element der Liste als sortierte Teilliste.\n", "2. Durchlaufe den Rest der Liste und tausche das aktuelle Elemente so lange mit seiner linken Nachbarin, bis die linke Nachbarin kleiner als das aktuell einzusortierende Element ist.\n", "3. Wenn das letzte Element der restlichen Liste an der richtigen Stelle eingefügt wurde, so ist die Liste sortiert.\n", "
" ] }, { "cell_type": "markdown", "id": "fb89beaa-28f9-473b-af1f-d5c781a1a3d0", "metadata": {}, "source": [ "So könnte eine Implementierung des Algorithmus in Julia aussehen. Probieren Sie auch diesen Algorithmus aus (in dem Sie die Zelle direkt hierdrunter ausführen mit STRG + Enter) - es werden jedes Mal neue zufällige Listen generiert und der Zustand der Liste nach jedem interessanten Schritt (Tauschen von Elementen) ausgegeben:" ] }, { "cell_type": "code", "execution_count": null, "id": "6f2c20ab-cd76-47d2-be97-f5ee4514e7ae", "metadata": {}, "outputs": [], "source": [ "function insertionsort(A)\n", " n = length(A)\n", " for i=1:n # Durchlaufe die Liste\n", " j = i # Index des aktuell einzusortierendem Elements\n", " while j>1 && A[j-1] > A[j] # Überprüfe ob Element links von aktuell einzusortierendem Element größer ist \n", " # (ob Element in sortierter Liste am Anfang noch weiter nach links rücken muss)\n", " \n", " println(\"Tauschen von \" * string(A[j-1]) * \" und \" * string(A[j])) # Ausgabe\n", " tmp = A[j-1]; # Tauschen von aktuellem Element nach links in sortierter Liste\n", " A[j-1] = A[j];\n", " A[j] = tmp;\n", " j = j-1 # Index des aktuell einzusortierendem Element aktualisieren\n", " println(A) # Ausgabe der Liste\n", " println()\n", " end\n", " end\n", " println(\"Sortierte Liste:\")\n", " println(A)\n", " return\n", "end" ] }, { "cell_type": "code", "execution_count": null, "id": "0819224a-bb7b-4982-9d5c-5876ad4ca851", "metadata": {}, "outputs": [], "source": [ "n = 10; # Länge der zu sortierenden Liste\n", "m = 100; # Maximaler (möglicher) Wert der zu sortierenden Liste\n", "\n", "A = rand(1:m, (n)); # 1:m gibt die Spanne der zu sortierenden Liste an; \n", " # \"(n)\" sagt Julia, dass es sich um einen Vektor (für unsere Zwecke ausreichend gute \"Liste\") handelt.\n", "\n", " # rand generiert uns mit den Informationen, die wir der Funktion liefern eine zufällige Liste \n", " # (in diesem Fall Vektor) mit Zahlen zwischen 1 und m\n", "\n", "println(\"Unsortierte (zufällige) Liste:\")\n", "println(A) # Ausgabe der zufälligen Liste vor Sortierung\n", "println()\n", "\n", "A = insertionsort(A);" ] }, { "cell_type": "markdown", "id": "4bcd1e0a-2dc8-43d8-bd90-f94f05017333", "metadata": {}, "source": [ "Wir wollen nun einige besondere Listen anschauen und schauen, wie der Algorithmus hier vorgeht im Vergleich zu Selectionsort. Wie oben beschrieben, interessieren uns vor allem die benötigten Operationen des Sortieralgorithmus zum Sortieren der Liste. Was beim Verwenden mit Selectionsort auffällt, ist, dass dieser stets die gleiche Anzahl an Operationen benötigt. Betrachte etwa folgende beiden Liste und deren Sortierungen:" ] }, { "cell_type": "code", "execution_count": null, "id": "2a14896c-7361-4dcc-b504-3d25a79d9c86", "metadata": {}, "outputs": [], "source": [ "A = [2, 1, 3, 4, 5, 6, 7, 8, 9, 10]\n", "B = [6, 7, 3, 8, 4, 9, 5, 10, 2, 1]\n", "\n", "println(\"Liste A\")\n", "selectionsort(A)\n", "println()\n", "println(\"Liste B\")\n", "selectionsort(B)" ] }, { "cell_type": "markdown", "id": "78496faa-b72e-4fd5-82d8-bac87cf8a2f7", "metadata": {}, "source": [ "In beiden Fällen tauscht und vergleicht Selectionsort gleich viele Elemente. Dies ist jedoch bei Insertionsort anders. Es gibt eine Liste, sodass Insertionsort beim Sortieren dieser Liste keine Elemente tauschen muss." ] }, { "cell_type": "markdown", "id": "3e8bbafd-6e31-4f25-91f9-37d029bf3a18", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Finden Sie eine Liste mit zehn Elementen mit den Zahlen zwischen eins und zehn, sodass unsere Implementation von Insertionsort keine Elemente tauschen muss.\n", " \n", "Hinweis: Unter dieser Box ist eine Box, wo die Liste eingegeben und ausprobiert werden kann.\n", " \n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "7388841d-8035-4305-bf03-c74680f7a318", "metadata": {}, "outputs": [], "source": [ "# Fügen Sie hier ihre Liste ein\n", "A = [ ] # Füllen Sie diese Liste mit ihren Zahlen z.B. [1,2,3]\n", "\n", "A = insertionsort(A) # Probieren Sie das Sortieren mit STRG+Enter aus und betrachten sie die Ausgabe" ] }, { "cell_type": "markdown", "id": "0b4a75e5-3b88-44d0-8c66-c3010b290105", "metadata": {}, "source": [ "Diesen Unterschied zwischen den benötigten Operationen (und somit Laufzeiten) zwischen (Sortier-)Algorithmen je nach Liste, die zu sortieren ist beschreibt man mit der Worst-, Average- und Best-Case Laufzeit. Die Bestcase Laufzeit von Insertionsort ist hierbei $\\mathcal{O}(n)$, da n Vergleiche vorgenommen werden, aber keine weiteren Operationen benötigt werden. Diese Unterscheidung spielt für Merge- und Selectionsort allerdings keine Rolle, da dessen Laufzeit, stets gleichbleibt, unabhängig von der genauen Zusammensetzung/dem Sortierungsgrad der Liste.
\n", "\n", "Nun bleibt noch die Frage, was eine Liste mit zehn Elementen wie oben sein könnte, sodass der Worst-Case für Insertionsort eintritt. Dies wollen wir in der folgenden letzten Aufgabe betrachten:" ] }, { "cell_type": "markdown", "id": "025b2914-33a3-4ec9-95a6-6890ee0a82f9", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Suchen Sie eine Liste mit zehn Elementen mit den Zahlen zwischen eins und zehn, sodass unsere Implementation von Insertionsort maximal viele Tausche durchführt. In welcher Komplexitätsklasse $\\mathcal{O}$ ist der Worst-Case von Insertionsort einzuordnen? (im Sinne der bestmöglichen Klasse)
\n", "Anders gefragt: Wieviele Operationen (Tauschen) werden in Abhängigkeit von der Länge der eingegebenen Liste gebraucht?\n", " \n", "Hinweis: Unten findet sich eine Box, wo die Liste eingegeben und ausprobiert werden kann.\n", " \n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "1f574d16-555c-4afb-9d19-a44f1b009d85", "metadata": {}, "outputs": [], "source": [ "# Fügen Sie hier ihre Liste ein\n", "A = [ ] # Füllen Sie diese Liste mit ihren Zahlen z.B. [1,2,3]\n", "\n", "A = insertionsort(A) # Probieren Sie das Sortieren mit STRG+Enter aus und betrachten sie die Ausgabe" ] }, { "cell_type": "markdown", "id": "016347d4-e81a-4179-99df-7453ea34efc5", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "6e0a042d-25db-4cb3-997b-6c9f8eaefe61", "metadata": {}, "source": [ "
\n", " \n", "### Rückblick-Aufgabe\n", "***\n", "Das Ziel dieses Projekts war es, das Sortieren von Listen genauer zu verstehen und einige mögliche Algorithmen zum Sortieren von Listen kennenzulernen. Insbesondere Mergesort unterscheidet sich in der Ausgefallenheit von den anderen beiden vorgestellten Algorithmen, Insertionsort und Selectionsort.\n", " \n", "Was glauben Sie, welche Relevanz Sortieralgorithmen im Alltag für Sie haben? Wenn Sie etwa Blätter oder ihre Handkarten bei einer Runde Karten sortieren. Verwenden Sie dort intuitiv einen Sortieralgorithmus und wenn ja welchen?\n", "
" ] }, { "cell_type": "markdown", "id": "6c8b5a5c-2dca-49b4-90d8-325b310ca18b", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "39c0f8d5-765c-4c26-8dcf-26e5b551f459", "metadata": { "jp-MarkdownHeadingCollapsed": true, "tags": [] }, "source": [ "### Literaturhinweise\n", "- Sorting algorithm. (2023). In Wikipedia, The free encyclopedia. https://en.wikipedia.org\n", "- Selectionsort. (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org\n", "- Mergesort. (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org\n", "- Totale ordnung. (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org/wiki/Ordnungsrelation" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.4.2", "language": "julia", "name": "julia-1.4" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.4.2" } }, "nbformat": 4, "nbformat_minor": 5 }