Video 7-1: Was ist sortieren?

0:03 Jetzt haben wir ganz ganz lange über alle möglichen Methodiken und trockenen Grundlagen gesprochen mit nur einzelnen Beispielen so ein bisschen zwischen reingestreut. Ähm jetzt drehen wir das für den Rest der Vorlesung um. Wir gehen durch verschiedene Beiträge für unseren Werkzeugkasten an Algorithmen und Datenstrukturen und gehen die ein bisschen systematischer durch. Problem nach Problem und dann Lösung für Lösung. Und wir fangen an mit dem vielleicht einfachsten davon, nämlich dem Sortieren. Dazu hatte ich ja schon vorhin aufgerufen, bisschen ihr ihre Ihr ihr Grundlagen oder ihr Vorwissen äh Kund zu tun. Äh Sleepsort. Ja. Äh ein ein Punkt, der sich beim Sortieren offenbart, ist, dass es viele Möglichkeiten gibt, die ans Ziel führen. Und das ist auch eine schöne Spielwiese, um irgendwelche Sachen auszuprobieren, ob sie jetzt ähm für die Anwendung relevant sind oder nicht. Das wird sich hier in dem Kapitel weiter wiederfinden.

1:07 Was haben wir vor? Wir schauen uns äh kurz an, worum es dem Problem geht. Das schaffen wir auf jeden Fall heute noch und werden vielleicht ein paar einfache Sortierverfahren schon anschauen. Ähm, die Stars der Show sind im wesentlichen Quicksort und Merchsort, die zwei Verfahren, die in der Praxis auch am relevantesten sind. Noch ein bisschen Theorie dazu machen und ein Abstecher zu Datenstrukturen und ein paar äh Kommentare ähm wie das in der Praxis läuft. Wie sie vielleicht wissen, war ich da auch mit beteiligt. Äh, mal schauen, wie viel Zeit wir dafür haben. Da muss ich ein bisschen äh haushalten.

1:43 Erstmal ein bisschen zu den Regeln, worum geht's hier überhaupt? Was ist sortieren? ähm in der konkreten Formulierung für uns kriegen wir ein Array von Objekten. Und das ist hier jetzt anders als im letzten Kapitel absichtlich äh etwas offen gehalten, denn der große Vorteil der ganzen Sortieralgorithmen, die wir hier betrachten, ist, dass sie nicht wissen müssen, was sie sortieren. Äh gleich noch ein paar Beispiele dazu, was das heißen kann. Na ja, und das Ziel ist äh dieses Array so umzuordnen, indem man Dinge vertauscht, dass hinterher die Objekte aufsteigend sortiert sind. Kleinstes vorne, größtes hinten und immer schön der Reihe nach jeder ist kleiner, kleiner gleich als der Nachfolger. Schauen wir uns ein paar Beispiele an, wo das vorkommt. Also einmal ähm eine Liste der deutschen Hochschulen.

2:41 Da ähm hat Wikipedia eine lange Liste mit allen möglichen Hochschulen aus Deutschland, die man nach diversen Kriterien sortieren kann. Sie kennen diese Tabellen, man klickt auf den Header. Äh, wenn man nach Gründungsjahr sortiert, dann muss man nicht so weit scrollen, bis man bei der Philips Uni ist. andere Sortierien muss man weiter scrollen. Okay, so rum sortiert ist nich sieben sieben Studies. Okay. Äh kann man gucken, was die größten Unis sind. Das natürlich Fern Unis ein bisschen geschummelt und so weiter und so fort. Äh, sie wissen, wie das funktioniert. Ich bleib bei Gründungsjahr als ein Beispiel.

3:23 Äh, man kann auch viele andere Dinge sortieren. Ähm, ein Beispiel, was auch noch immer wieder relevant ist, sind die Abwartszeiten von irgendwelchen Zügen. Wenn Sie dann so nach der Sortierung fahren, da habe ich als Objekte die Züge oder die Abfahrten von Zügen und sortiert eben nach der Zeit. äh wird knapp, wenn Sie jetzt einen von denen nehmen wollten. Ähm anderes Beispiel, Sie kennen unsere Fachbereichswebsite und nur für sozusagen den Zweifel, dass Sie das noch nicht gesehen haben, gibt's hier eine alphabetisch sortierte Liste der Arbeitsgruppen und wenn man eben Wildheiter wild heißt, dann ist die Wahrscheinlichkeit groß, dass man gegen Ende auftaucht.

4:09 Natürlich gibt's jede Menge andere Beispiele. Sie haben vielleicht auch schon mal was in dem physischen Index von dem Buch nachgeschlagen, die sind auch sortiert. Also jede Menge Dinge, was die Beispiele zeigen sollen, ist üblicherweise haben wir kompliziertere Dinge, Züge, Abfahrten oder Universitäten, die man in verschiedene Art und Weise sortieren könnte oder es gibt verschiedene Kriterien, nach denen man sortieren könnte und die können alles Sinn ergeben. Das heißt, eigentlich wollen wir als Teil der Eingabe nicht nur die Objekte haben, sondern auch ein Sortierkriterium. Wonach hätten wir sie gerne sortiert? Und da werden wir kurz drüber reden müssen, wie das aussieht, denn ähm das ist erstmal eine abstrakte Sache. Was heißt das? Ein Sortierkriterium mitübergeben.

4:57 Das Angenehme dann ist, dass ich jede Menge Anwendung mit dem gleichen Algorithmus bzw. sogar dem gleichen Code erschlagen kann. Da sind hier so ein paar Beispiele, äh die sind jetzt ähm erstmal aus dem Kontext gerissen, vielleicht nicht unfassbar spannend. Äh, das erste Beispiel liest eine Zahl ein und legt dann ein Array von zufälligen Zahlen zwischen 0 und 1 an mit dieser äh mit Bibliotheksmethode und sortiert die dann hinterher. Können sich fragen, warum macht das Sinn? Aber ähm da gibt's gibt's schöne Anwendung für, die auch äh im Buch vorkommen. Der gleiche Code, also hier diese Insertion Sort, den Sie in der Bibliothek dort auch finden. Der gleiche Code kann neben diesen Doubles auch Strings hand haben. Also ich könnte z.B. aus einer Datei alle Strings einlesen, z.B. diese Wörter mit drei Buchstaben und die dann sortieren. Warum? Na ja, warum nicht? Aber äh der gleiche Code ähm kann eben mit Strings auch umgehen und würde die dann lexikografisch sortieren.

6:08 Also Strings, drittes Beispiel könnte ein kleines Programm sein, das quasi das das Unix LS oder das äh Windows Dear oder DOS Dear umsetzt. Ich äh kann es aufrufen und dann listet es die Dateien in diesem Ordner in alphabetischer Reihenfolge. Ähm geht in Java auch relativ kompakt mit der mit dem F mit der Filklasse. Da kann man sich ein Array der Files in diesem Verzeichnis geben lassen und das sortieren. Und da ist dann auch der Default, dass man diese Dateien alphabetisch, lexigographisch alphabetisch sortiert nach ihrem Dateinamen. Auch bei Dateien könnte ich natürlich andere Dinge tun. Könnt auch nach Größe sortieren oder sonst nach Datum, wie auch immer. ALDOS geht also mit dem gleichen Java Code. Wie funktioniert das? Damit Sortieren wohl definiert ist, brauchen wir ein Kriterium, das mathematisch gesprochen eine totale Ordnung darstellt. Ähm, informell heißt es einfach nur, dass die Vergleiche, die wir machen, keinen Quatsch ergeben. Aber ein bisschen formaler, um es einmal ähm auf der Folie zu haben, ist eine totale Ordnung, eine Relation, die diese äh äh diese Bedingung erfüllt.

7:25 Und an der Stelle ähm erinnere ich mich früh im Studium fand ich das eine Hürde, deswegen versuche ich das ein bisschen langsam zu machen. Am Ende möchten Sie, wenn sie Dinge formalisieren, wenn wir ganz präzise uns ausdrücken wollen, alles als Mengentheorie Ausdrücke schreiben. Alles ist eine Menge oder eine Menge von Mengen oder eine Menge, eine Funktion von einer Menge in die andere und all diese Dinge. Eine Relation ist eine Teilmenge von so einer ähm von so einem kathesischen Produkt. Also streng genommen ist das kleiner gleich eine Menge und die enthält diese Menge enthält alle Paare, die geordnet sind. Also wir würden, wenn X und Y in dieser Menge kleiner gleich enthalten sind, dann schreiben wir das landläufig als X klein = Y mit so einer Infixation. Das ist aber reiner syntaktischer Zucker, den wir uns erlauben, damit es schöner aussieht. Wenn Sie es mengenthoretisch formulieren möchten, könnte man es so schreiben. Das Paar XY ist Element der Relation.

8:31 In dem Sinne macht diese diese Schreibweise Sinn. Dann ist eine Relation, eine Teilmenge von diesen Paaren und wir möchten nicht beliebige Teilmengen von Paaren, sondern nur solche, die diese Eigenschaften hier erfüllen, die machen sin Sinn für eine Relation und die Eigenschaften sind eben einerseits jedes Element ist kleiner gleich sich selbst, weil es gleich sich selbst ist, aber muss man eben explizit dazu sagen. Antisymmetrie heißt, dass wir äh wenn zwei Elemente in beide Richtungen vergleichbar sind, dass die dann auch gleich sein sollen. Es darf also keine bezüglich der Relation ununterscheidbaren Elemente geben, die aber nicht identisch sind. Das ist zumindest hier in der in der strengen Version für eine totale Ordnung gefordert. Äh Transitivität ist das, was wir fürs Sortieren unbedingt brauchen, weil die ganzen Algorithmen darauf aufbauen werden, dass wenn x kleiner ist als y und y kleiner ist als z, dass ich dann x und z nicht noch mal vergleichen muss. Für alle sinnvollen, denkbaren Dinge äh ist das erfüllt, aber man muss es äh sich einmal klar machen, dass diese dass es diese Eigenschaft haben muss, damit die Ordnung Sinner gibt. Und Totalität heißt noch, dass äh alle zwei Objekte in die eine oder in die andere Richtung geordnet sind.

9:52 Was könnte schiefgehen? Hier sind zwei Antibeispiele. Äh, wenn Sie die Relation nehmen, die mir sagt, welche der drei ähm Zeichen, Strategien, Aktion, Aktion vielleicht bei Schere, Stein, Papier, gegen welche andere gewinnt, dann habe ich eben die Schere, die gegen Papier gewinnt und Papier gewinnt gegen Stein und Stein gewinnt gegen Schere. Das heißt, ich kann die nicht ordnen, weil das diese Relation einen Kreis enthält und das wiederum verletzt z.B. die Transitivität.

10:32 Ja, Schere ist kleiner als Papier, andersrum. Papier ist kleiner als Schere. Schere ist kleiner als Stein, dann müsste auch Papier kleiner als Stein sein. Ist aber genau umgekehrt. Deswegen ist das keine Ordnungsrelation.

10:46 Das ist irgendeine andere Relation, aber ich kann damit nicht sortieren. Und ein Beispiel, wo die restlichen Kriterien erfüllt sind, aber Totalität eben nicht, ist die Teilbarkeit. Also, ich kann mehrere Elemente haben, die unvergleichbar sind, keines teilt das andere. Wir sind noch wach, ohne dass es ein Widerspruch gibt, also wann immer ich relativ prime Zahlen habe.

11:19 Da mein Laptop vorhin gestreikt hat, dürfen Sie auch einmal technischen Ärger verursachen. Hm. Also, ich kann ja einfach lauter sprechen. Ist ja gar kein Thema.

11:50 Gut, dann machen wir jetzt an der Stelle eh eine ähm sozusagen einmal äh Interaktion und sie lassen sich nicht ablenken. Äh ist ja eine softte Frage. Kann ich auch direkt auf die Antworten wechseln. Mir geht's so ein bisschen darum, wie wie sehr sie damit in Berührung gekommen sind. Vielleicht haben sie sich über totale Ordnungsrelation in dem Kontext nicht so viel Gedanken gemacht, aber vielleicht haben sie es doch äh schon verwendet in irgendeinem Programmierprojekt.

12:51 Jetzt warten noch alle gespannt, wer da dann jetzt zu diesem Laptop zurückkehrt. Also, ich würde sagen, so um und bei die Hälfte hat äh das nicht aktiv benutzt und von den anderen ähm sie dürften, glaube ich, auch mehrere Sachen anhaken, richtig? Genau. Ähm, also nicht klar, ob sich diese Zahlen hier zusammen addidieren sollen, zum Rest eher nicht, ne? Äh, die meisten werden es in Java verwendet haben und vielleicht noch irgendwo anders. Äh, dementsprechend insbesondere für die Leute hier in dem ersten Balken, lassen Sie mich das äh noch einmal in Ruhe sagen, was da passiert. Wie können wir so eine Ordnungsrelation in Code gießen, wenn also das völlig beliebig sein soll? Ich möchte beliebige Sortierkriterien angeben können. Wenn jemand sich traut hinzugehen, könnte Also ich bin ja gewohnt mit vier Kindern nebend dran zu arbeiten. Ich kann das völlig ausblenden, aber ich weiß nicht, ob das für alle anderen gilt. Und Wecker verschlafen ist vielleicht auch einfach. Wie leicht ist da der Übung?

14:21 Ach, Schnille. Genau. Wie übergeben wir einem Programm ein eine beliebige Ordnungsrelation, das von Mengenle und von Reflexivität noch nie was gehört hat? Äh, eine übliche Variante ist ein sogenannter Callback. Also, wir übergeben etwas und wann immer das Programm eine Frage hat, welches von diesen zwei Objekten ist denn größer, ruft es mich zurück und sagt: "Guck mal, ich habe hier diese beiden. Sag mal eben, welches ist größer?" Äh, das ist die Idee. Ähm, Formal ist ein Callback eine Funktion, die man aufrufen kann. Wir telefonieren natürlich nicht wirklich. Äh, in Java kann man das als ein Interface realisieren. Heißt Comparable. kommen wir gleich zu eben enthält das enthält so eine Methode mit der man diesen Vergleich realisieren kann. Mittlerweile kann Java ja auch zumindest der Syntax nach echte Lambda Ausdrücke und Funktionen. Die sind natürlich, wenn die dann auf der JWM kompiliert sind, sind das auch wieder ähm anonyme innere Klassen. Aber zumindest von der Syntax her ist Java da jetzt ähm genauso äh modern wie sagen wir äh C++ oder Python.

15:34 Ähm, wenn Sie sich fragen, wie das auf Hardwarebene realisiert wird, dann ist es gerade in Che andes als eine Stelle im Speicher, an die ich springen kann und von da Programmcode ausführen kann. Ist das einfach ein Pointer auf ein Stück Code. Viel mehr muss ein Callback nicht sein. In den modernen Speicher sicheren Sprachen wird es gekapselt, damit man nicht an beliebige Stellen springt und irgendwas ausführt, was gar kein Code ist. Abgesehen davon, von der reinen Funktionalität, ist es eine einfache Sache. Ähm bieten quasi alle Programmiersprachen in der einen oder anderen Geschmacksrichtung an. Wie sieht es konkret aus? Ähm, das sind verschiedene Teile, die da zusammenspielen. Deswegen gibt's hier so ein Überblick. Der Callback selbst ist Teil von diesem Comparable Interface.

16:27 Kann also für die Objekte, die ich sortiere, sagen, die sind comparable. Das heißt, die implementieren so eine Methode Compare to. Damit kann ich ein Objekt mit einem anderen Objekt dieser gleichen Klasse vergleichen. In meiner Sortierimplementierung würde ich dann sagen, ah, ich erwarte ein Array nicht beliebige Objekte, bei denen weiß ich nicht, was ich tun soll. Kleines Sternchen dran, kommen wir gleich noch zu. Gibt noch eine zweite Option. Ähm, nicht beliebige Objekte, sondern comparable Objekte. Die kann ich miteinander vergleichen. Das heißt, wann immer der Algorithmus die Frage hat, ist Aj kleiner als Aj -1? Frage ich einfach AJ, wie sieht's aus? Bist du kleiner als AJ -1?

17:19 Der Datentyp, den wir vielleicht selbst implementieren, wenn wir einen eigenen brauchen, der kann dann eben comparable implementieren und eine entsprechende Methode haben, die das compare to umsetzt. Und von außen sieht man das, wenn man ein entsprechendes Objekt verwendet, gar nicht. Hier taucht Comparable nirgends auf. Es ist einfach nur implizit String. Ein Subtyp von Comparable implementiert dieses Interface und hat entsprechend eine solche Methode, die es halt schon gibt. Das heißt, wir müssen die nicht neu bauen an der Stelle.

17:52 Jetzt haben Sie vielleicht hier gesehen, dass Compared to in Java diese mysteriösen Rückgabewerte -1 + 1 0 hat. Äh, wie könnte so ein Callback aussehen? Eine klassischere Methode wäre zu sagen oder was was in in C verwendet wurde, z.B. wäre zu sagen, ich habe eine Funktion echt kleiner alles. Dann gebe ich zwei Objekte rein und rauskommt ja oder nein. Äh in Java hat man sich entschlossen eine ein so ein dreiwege Vergleich zu machen. Siehen sich hatte ich bei biner Suche vorhin schon angesprochen. Das heißt, der der Rückgabewert ist einer dieser drei Fälle, ob die Objekte entweder gleich sind oder das eine oder das andere größer ist. Und das kann ich eben mit einer Zahl, die null negativ oder positiv ist, codieren. Und sie sollten sich immer ähm immer im im Kopf halten, dass wir sozusagen compare to mit einem Minus ersetzen.

18:56 Das ist so wie Bau - W und dann ist das Ergebnis bezüglich 0. Das gleiche wie vielleicht sollte ich hier nicht kleiner gleich schreiben, sondern Fragezeichen 0. Wenn die Differenz kleiner als 0 ist, dann gebe ich -1 zurück. Dann wäre äh Warum hab wir das denn jetzt hier andersrum? Oh, wie die verwen mich jetzt aber ähm hier ist V kleiner als W, ne? Genau. Kleiner null. Passt schon. schweres Gewichtes und Balkenwagen sind ja komplizierte Objekte. Also, wenn V - W negativ ist, dann war V kleiner als W. Dementsprechend sind wir in diesem Fall. Äh, passt zusammen. Das ist meine meine Eselsbrücke ist V compared to W soll als Rückgabewert das haben, was ich bekomme, wenn ich die voneinander abziehe und mit null vergleiche.

19:56 Das ist implementiert für die üblichen Verdächtigen aus der Java Bibliothek. Wo immer es Sinn macht, hat die Bibliothek so eine Compar to Funktion schon eingebaut. Ähm und für eigene Klassen müssen wir es dann eben implementieren. Als ein Beispiel ist hier eine Dateeklasse, die Sie in dieser Form natürlich nicht bauen brauchen, weil Sie die auch schon in der Bibliothek finden. Aber als Illustration, wie das aussehen könnte, wie würde man normalerweise Daten sortieren wollen? Ähm erst nach Jahr, dann nach Monat, dann nach Tag. Eine lexikografische Ordnung nach den Tuppeln. Das heißt, um mein aktuelles Date mit einem anderen zu vergleichen, prüfe ich erst, wenn mein Jahr echt kleiner ist als das anderen, dann gebe ich -1 zurück. Wieder denken sich das abziehen, das Minus. Ähm, umgekehrt, wenn mein Jahr echt größer ist, gebe ich +1 zurück. Letzter Fall, die sind beide gleich, dann vergleiche ich die Monate und so weiter und so fort. Das ist so der der übliche ähm das übliche Schema, nachdem diese Compare to Methoden aufgebaut sind. Ich habe so eine äh hierarchische Reihenfolge, in der ich die Dinge sortiere. Das ist der der typische Fall.

21:12 Dann gehe ich die einzel nach dem anderen durch. Theoretisch könnte man auch hier, wenn ich weiß, dass die zwei Zahlen unterschiedlich sind, einfach die Differenz zurückgeben. Also ich könnte bei zwei Integen das hier zwei Zahlen sind, könnte ich im Prinzip x - y zurückgeben und das würde der üblichen Ordnung der Zahlen entsprechen. Man macht es deshalb ungerne, weil man sich dann Gedanken um Overflows machen muss. Insbesondere wissen Sie vielleicht, dass man eine eins kleinere Zahl bei den negativen Zahlen darstellen kann als bei den positiven Zahlen. Und um also diesen ähm Randfällen aus dem Weg zu gehen, ersetzt man die Differenz zurückzugeben durch solche Ifkaskaden. Dann hat man den den Randfall auch korrekt mit erschlagen, den man sonst ähm wo man sich zumindest sonst Gedanken machen müsste, dass man den nicht äh falsch behandelt. Dann ein letzter Punkt noch. Dieses Comparable Interface kann ich einmal implementieren. Das heißt, ich kann meinen Universitäten eine Ordnung geben nach Gründungsjahr und das war's dann.

22:33 Was anderes sortieren geht nicht, das ist nicht immer bequem. Deswegen gibt's noch eine zweite Variante, in der ich ein externes Objekt übergebe, einen Comparator, der wirklich diesen Callback genauer wiederspiegelt. Den kann ich anrufen und fragen, hier sind zwei Objekte. Was denkst du denn, welches von denen größer ist? Und dann kann ich verschiedene Meinungen haben mit verschiedenen Comparators.

22:59 Äh, so sieht das Interface aus. Also, der bekommt Objekte vom Typ T, generische Klassen, wenn man uns noch ein bisschen ähm drüber unterhalten in diesem Kontext und hat eine Methode Compare, gleiche Semantik wie compare to, also hier wieder mein äh meine Eselsbrücke noch mal formuliert mit diesem Platzhalt dafür kleiner, größer ist gleich. Äh vielleicht hilft's ihn. Wenn nicht, dann vergessen Sie es und merken Sie sich irgendwie anders. Also in ähm meinem Code werde ich eher diese Comparator Variante verwenden, weil die halt immer funktioniert. Der Crick Way Code verwendet comparable, weil man den Code noch ein paar Zeichen kompakter machen kann. Dürfen sich dann aussuchen, welches ihnen lieber ist. Die ganze Java Bibliothek enthält die Sortiermethoden immer in zwei Kopien. einmal mit comparable und einmal als beliebige Objekte mit Comparator.