[Playlisten] [Impressum und Datenschutzerklärung]

12A.3 Algorithmen, Suchen und Sortieren, Bubble Sort, Quicksort, Laufzeit, O(n log(n))


CC-BY-NC-SA 3.0

Tempo:

Anklickbares Transkript:

das erste große Thema – in der Informatik – ist – typischerweise – Datenstrukturen – und Algorithmen – Datenstrukturen – hatte ich ihn letztes mal ansatzweise – erzählt das ganze Semester mit verbringen – wie bring ich meine Daten unter – und wie komme ich wieder dran – was sie Warteschlange – und den Stack was ich vorgeführt hatte war – Spaß mit Schecks – eine Matrix mit ganz vielen Nullen – und einigen – anderen Zahlen – sowas sind Datenstrukturen – ähm – was ich heute – ganz grob einmal zeigen will tiefer werden wenn ich eingehen – auf ?? Semester normal Informatik – ist – Algorithmen – was für Gedanken gibt es hinter Algorithmen wie beurteile ich Algorithmen – wie messe ich Algorithmen also Rechenverfahren – oder Problem Löseverfahren – wie gehe ich bestimmte – Probleme rezeptartig – an – das – heißt Algorithmus – wie gehe ich ein Problem rezeptartig – an – einen – einlöse Verfahren – oder wenn's um Zahlen geht ein – Rechenverfahren – und die typischen Sachen die man sich da anguckt es gibt diverse andere aber was man sich da ganz ausführlich anguckt in der normalen Informatikstudium – wäre Suchen und Sortieren – gegeben eine Menge von Objekten wie kann ich darin ein bestimmtes – wieder finden – gibt mir die Bestellung mit der Nummer soundsoviel – finde mir den Datensatz – zum Zeitpunkt – so zu viel – und sortieren – lassen zu den beiden großen – Eckpfeiler bei den Algorithmen – das möchte ich ?? zum bisschen anschneiden insbesondere – das Sortieren – an das Suchen ist denke ich Ihnen in der praktischen Relevanz klar sie geben in irgendeiner – ?? natürlich klar welche Suchmaschine ein Begriff ein und finden so zu viel tausend oder Millionen Webseiten das ganze etwas mit Suchen zu tun – in irgendwelchen Verzeichnissen versuchen im Telefonbuch – nachschlagen – wird immer zu Fuß machen – im Wörterbuch nachschlagen ?? es war – dann elektronisch machen – all das hat was mit Suchen zu tun das kommt und scheint – recht häufig vor – das Sortieren – kann man sich im Alltag gleich nicht so gut vorstellen wann muss ich irgendwelche Datenmengen – sortieren – das lustige Weise ist – ist das Sortieren – oft eingebaut in der Suchen – stellen Sie sich das Telefonbuch – vor – warum ist das Telefonbuch – hilfreich zum zu suchen – ?? es ist deshalb hilfreich Komma dass man sich deshalb hilfreich weil's – sortiert diese sind vorne mit A an und hört hinten mit Z auf das Telefonbuch nicht sortiert wäre – nach den Anfangsbuchstaben – wird es ziemlich sinnlos – müsste jemand das halbe Telefonbuch durchgucken und jemand zu finden – dass – ein ein wesentliches Prinzip die Suche zu beschleunigen – ist seine Daten zu sortieren – nicht Telefonbuch – an – der Informatik ?? das ?? noch ein ganz eigenes Kapitel – Lustigerweise – ist es dann recht einfach kommen seine Daten erst mal sortiert hat ist es recht einfach und recht schnell zu suchen – insofern macht man aus dem Sortieren als eigenes Kapitel – es gibt auch – interessante Anwendung für sortieren ohne das Suchen – aber eher weniger muss ich gestehen – was ich jetzt bringen will – ist normal in Sortieren rein zu gucken ich glaube ich verdamme – noch mal irgendwo noch kurz was zu suchen sagen aber das was ich heute erzählen wir das Sortieren was ist eigentlich – der Kern des Ganzen – was ist der Pilzalgorithmus – überhaupt – was ein etwas besserer Algorithmus dafür ein – Problem Löseverfahren – zum Sortieren – wie kann ich denn überhaupt sagen dass das – besser oder schlechter ist – das – was man an der Stelle traditionellerweise – macht – Analog – beim ersten Programm an mit Hello World – und das erste Sortierverfahren – was man sich anguckt des Bubblesort – extrem ineffizient – aber – gut zu programmieren – als es gar nicht mal so das das nie verwendet würde wenn ich auf die Schnelle was hinschreiben muss und habe kein Sortierverfahren – fertig vorbereitet irgendwo – und möchte das das in einer Minute zu Ende programmiert ist – warum nicht es ist nur eben – super langsam – das sehen wir gleich – die Idee beim Bubblesort ist folgendes sie haben eine – ihre Daten in irgendeiner Liste – an – den sowas sie haben ihre Daten in einer Liste gegeben – das Ziel ist diese Liste – zu sortieren ?? möchte auf lange Sicht dahin – dass die zweiundvierzig – oben steht und die fünf unten – ?? gucken dann käme – kommt zweimal interessant ?? siebzehn kommt zweimal – und dann kommt die fünfundzwanzig – und einunddreißig – also das hier ist gegeben – dass sie hinten ist was ich haben will – gewünscht – gewünscht – Eingabe und Ausgabe – für diesen Algorithmus – und was man und tut beim Bubblesort – Gläschen – Bubbles – aufsteigende – Bläschen was man guckt ist fängt – vorne an – Vergleich die ersten beiden und guckt ob die den Schummer in der richtigen Reihenfolge sind – anscheinend nicht ?? also tauscht man die aus – als ob die siebzehn aufsteigt – die höheren Zahlen steigen auf ?? Luftbläschen – so – fünf – siebzehn – fünfundzwanzig – einunddreißig – siebzehn – zweiundvierzig – jetzt guck ich mir die nächsten beiden an – okay – die sind in der richtigen Reihenfolge – gucken wir diese beiden Anfang zwanzig einunddreißig sind auch in der richtigen Reihenfolge der muss nicht aufsteigen ?? einunddreißig – siebzehnten in der falschen Reihenfolge – die große Zahl nach oben – die beiden ?? aus einundneunzig – siebzehn – fünf – und – da guck ich mir die beiden oben an ein dreißig Landwirte sind auch in der richtigen Reihenfolge – aber – da muss immer von unten anfangen sie sehen wenn ich das veranstalte – gibt's immer noch Stellen an den Blödsinn passiert von zwanzig siebzehn – ?? ist zwar alles – einstelle – feucht aufgestiegen verzögern erstellen Beistrich in dann an der Wischer was kann immer noch sein das irgendwas übrig geblieben ist wie die fünfunddreißig siebzehn das heißt im nächsten Schritt mal das ganze – Komma von vorne gucken unten – fünf siebzehn richtig siebzehnten zwanzig richtige Reihenfolge für ?? zwanzig siebzehn falsche Reihenfolge – muss stehen siebzehn fünfundzwanzig – und so weiter – und so weiter also ich gehe von unten nach oben jeweils zwei übereinanderliegende – an ob ich die austauschen muss – wenn ich dann fertig bin um angekommen bin – und wahrscheinlich noch ein Durchgang – noch ein ?? noch einen gleich noch ein ?? und zum Schluss werden die Zahlen der richtigen Reihenfolge – sitzen das ist der Gedanke hinter – Bubblesort – das Programmiermesser – auf die Schnelle – nur – ich baue mir es mal irgend ein Erreger sich sortieren will – man – Komma – vielleicht – maximal tausend Stück – dieses ?? setzt sich nicht in die Funktion rein einfach nur um Speicherplatz – an einer Stelle – anzulegen wenn es in die Funktion reinsetzen wäre es eigentlich schöner – an – der Stelle steht fehlt ihr der Speicherplatz als rechts außen hinsetzen das ist reintechnischer – Grund – kosmetischer Seil soll es lieber in Ansätzen einsetzen – den Unterschied habe ich nie richtig besprochen – es auch nicht – weiter sprechen Baums außen – wenn sie etwas mehr Speicherplatz gibt als in – die Nachbauten wollen statische Variablenverhältnis – zu Variablen die auf dem Stack angelegt werden – so die Sirene möchte ich mit Zufallszahl – füllen und dann sortieren – Zufallszahl – für ?? netterweise nicht so – schwierig – vor in – sinnvoller Weise gleich null – plus plus – ich gehe dieses RE durch – und schreibe Zufallszahl – rein diesen ?? eingebaut – in meinem Funktion liefert mir Zufallszahl – sollte Zufallszahl – vorhersagbar – die Zufallszahl – aber sie sind ziemlich zufällig aus – und die Rentenfunktion – ist deklariert – in Standardlipp – Punkt Ha – so jetzt habe ich ein rät das mit Zufallszahl – gefüllt ist – und jetzt möchte ich einfach – das sortieren lassen sinnvollerweise – schreibe ich das ganze sortieren in eine Extrafunktion – Bubblesort – großen es Arbeitsort – ist Punkt aus Bubblesort – der Funktion möchte ich sagen was sortiert werden soll – dieses Ray – und sie ist ja dumm sie weiß nicht wie groß eine Ray ist – außerhalb – von Erstellung – angelegt hat ?? an deshalb schreibe ich hier jetzt noch ein okay das Ding hat tausend – Einträge Satire dieses äh Jahr – und ich sage der Funktion obendrein etwa tausend Einträge in den höheren Sprachen müssen sie nicht mehr sagen dass das tausend Einträge hat – also was bitte noch Konstruktionen – bei denen die Sprache das weiß dass dieses RE tausend Einträge hat – so eine von zum Bubblesort nimmt eine Reihe und eine Anzahl für – eine Funktion Bubblesort – ein RE – nennen wir das einfach mal Punkt – war – mich – wobei dieses A – ist nicht mit dem A zu tun hat – beziehungsweise – Thema zu tun hat ja das eine ganz neue – Bedeutung – Arm und die Anzahl in Teint – wie viele stehen drin – die möchte ich sortieren – nun – was sollte dieser – Funktion Bubblesort zurückgeben das bisher noch nicht geschrieben – was soll sie zurückgeben ✂ in nahe liegende Gedanke diese ist das diese Funktion Bubblesort ein Reh zurückgibt – und das mit den ?? Racing C – eher ungeschickt – eine Reihe zurückgeben gibt es wirklich Punkt ich kann ein Zeiger auf eine Reihe zu dem ich müsste diese Speicherplätze – anlegen – irgendwo noch Speicher reservieren das macht es alles sehr ungeschickt – der Trick den man nutzt ist folgender Mann gibt keine Rei zurück sondern man sortiert einfach das äh was ein ?? übergeben wird – jeglicher – nur die Adresse des ersten Eintrags – in das bei – euch welche Hausnummer sie das REM Speicher – und die Funktion wird jetzt ganz frech sein sie nimmt sich dieses Array an der Einstellung groß im Speicher steht und sortiert es da – gibt kein neues Gerät zurück eine Kopie davon wieder zurück sondern sie sortiert es an Ort und Stelle – in Places – das wäre so das übliche Vorgehen in C damit man nicht bereits durch die Gegend reichen muss das es immer bisschen ungeschickt – Stein – soweit alles funktioniert – Punkt Mac – versetzt man sich aber anscheinend ein Prozessor hier eingestellt – der nicht tausend – Einträge kann – Prozessor einstellen – erinnere – vier drei sechs – der darf mehr – okay – also je nach Prozessor haben sie Platz für diese tausend ins zwei tausend Bytes oder nicht ?? damit einen eingestellter – Platz dafür hat – er zwei tausend dreizehn – an – was mache ich nun in den Bubblesort – in der Funktion Bubblesort wie gehe ich vor ✂ sollte von unten nach oben es mal gucken ob der untere echt größer ist – der untere echt größer ist als der darüber der nächste echt größer ist als der darüber in die gleich sind sicher nicht tauschen ?? Gleichzeichen – ?? Bindestrich austausche als guck ob der Unterricht größer Komma in einer for-Schleife von unten nach oben allerdings habe im ersten Durchgang die erste Blase wieder aufsteigt ich musste noch dafür sorgen dass ich mehrere Durchgänge habe – schon im ersten Durchgang – in einer for-Schleife – von – null – klein H das überlegen und klein noch mal – plus plus – nebenbei hier schreib jetzt wieder ganz dreist I für die Variablen der Vorschlag ?? steht auch schon die – aber diese beiden Unis haben nichts miteinander zu tun die leben in getrennten – Schweifklammer – dass die nur in dieser Schweifklammer – das wiederum dem ?? in der Schweifklammer zwei ganz – unabhängige dies – so das soll jetzt das – aufsteigen einer Blase sein ich gucke nach ob der – Akt zu Elle größer ist als der nächste – echt größer ist als der nächste ist der aktuelle – nicht größer als der nächste – sieht wie – das eins – wenn das der Fall ist dann muss ich die beiden austauschen – wenn ich den eben nicht – kriegen Sie das hin kriegen die beiden – ausgetauscht ✂ zwei Speicherstellen – stehen ähnliche Zahlen drin – vorher – und nachher sollen die beiden ausgetauscht – sein – wenn Sie das in – das ?? Mini Algorithmus – da das ✂ sinnvolle Verfahren ist eine zwischen zu speichern sie merken sich zum Beispiel – die dreizehn – in einer extra Speicherstelle – auf mal – doch ich merke mir die dreizehn er eine extra Speicherstelle – schreibe die zweiundvierzig – da oben hin – und schreibe dann die dreizehn mit zweiundvierzig – das ist die übliche Lösung – eine extra Speicherstelle – des jedermann das total raffiniert macht und etwas Speicherstelle aber das will ich lieber nicht vor – versteht kein Mensch insofern ist das Beste – ein Extraspeicher zu haben also ein letzter Speicherstelle – für mein – Haar von ihm – ?? – jetzt und – jetzt schreibe ich in dieses Ar von I den andern – kann ich jetzt hemmungslos überschreiben weil ich ihn mir in B gemerkt habe – schreibe ich rein – und jetzt habe ich für den immer noch den neuen Wert in – B so sehr das Observer das aus – den Wert von A von ihm merken – auf von ihm mit dem anderen überschreiben und den andern jetzt mit der überschreitenden habe ich die beiden ausgetauscht – das wäre ein Schleifendurchgang – für Bubblesort – an – wie oft muss ich den machen – vielleicht ✂ ein ein billiger Trick sich das einfach am Modell ihr anzugucken wenn ich sechs Zahlen – auf diese Weise verarbeiten will vergleiche ich die ersten beiden – Vergleich einzig vergleiche die zweiten beiden Vergleich zwei drei vier – fünf – sie nicht auch für die sechs Zahlen fünf Vergleiche – so würde ich mir das – überlegen Komma mit Hand voll Zahlen ausprobieren als gaben sie für sechs Saal fünf Vergleiche brauchen warum sie für tausend zwei – hundert neunundneunzig vergleiche oder für ähm – jährliche allgemein ähm reingeschrieben – bräuchte ich in minus eins – vergleiche – ich denke mit Null an – so verdient es wirklich ein minus eins vergleiche – man sieht es auch hier an dem E-Plus eins wenn ich hier bis Ende gehen würde – wäre ihm das als ein kleines Problem – N minus eins der Nautilus einziehen – wenn ich hier nur bis N minus zwei gehen würde für dich nicht alle in der Liste durchlaufen – kenne nicht eine Liste vor das wäre auch komisch aus dessen Warnzeichen das nicht funktioniert – wie soll das Ende des eins stehen – soweit – ist das jetzt ein Durchlauf – für dieses Bubblesort – der erste Durchlauf – jetzt kann es aber sein dass sich weitere Durchläufe – bräuchte – was mache ich ✂ also diese for-Schleife gehört noch mal in eine for-Schleife – sinnvollerweise – ist gleich null ?? – J – klein A – dass es wahrscheinlich zu viel dort kleiner N wenn ich für die tausend – Elemente täglich tausend Durchgänge mache alle ich bin faul mir das jetzt überlegen das das ?? Komma Stinnes macht den Braten nicht fett ob sie – dann entsprechend – eine ?? minus zwei hundert seine – schreib das auf der sicheren Seite – das größte Element ganz unten steht – Eier werde ich mit Entvertauschung – und von dem was unten sicherlich am Ziel sein nicht zu viel aber – wird funktioniert muss nicht lange nachdenken was diese bessere Lösung – an Komma das wäre erst mal die – brutale Lösung – ich mache das ganze tausendmal – Logik müsste man eigentlich schon das ganze in Aktion sehen können – zur Optimierung mal ausschalten um – Überraschungen – beim Einzelschrittmodus – vorzubeugen – dieses Handy will ich nicht ich will – es – der Text haben da es meine variable A – bisher steht noch nichts drin – so – jetzt sind Zufallszahlen – drin das war die for-Schleife mit den Zufallszahlen – unterstehen sie diese Tabelle mit tausend Zufallszahl – und jetzt kommt Bubblesort – ein matter den – weiter – was in etwas beschäftigt offensichtlich – Coaching – vielfach nicht haben – hättest dich mit tausend machen soll – ?? das – zeigt schon den Punkt – auf den ich hinaus will es gibt zu es gibt Sortierverfahren – die sind schneller und es gibt Sortierverfahren – die sind langsamer – erscheinen jetzt gerade ein zu haben – dass wir langsam – anderseits – könnte jetzt aber anhalten und gucken ?? weiter gekommen Beistrich als ihn mal an H – naja – so schlecht sieht es eher gar nicht mehr aus – und sie es mittendrin – einmal gerade gucken bei welchem Durchgang – er ist – anscheinend schon viel zu weit mitgemacht jetzt seine ähm durchgängige ganz Pflicht schuldig – und es erscheint schon längst fertig ohne dass das weiß – gucken bei den Blockes – okay ?? hat jetzt acht hundert zwei neunzig von den äußeren – neunzehn hundert achtzehn zwei neunzig von tausend ist aber anscheinend denk ich schon fertig sowieso Blattes ganz gemerkt – in die Liste sieht doch schon sehr – sortiert aus doch – an den okay aber noch ein schief stimmt der Mist jetzt also noch weiter aufsteigen – ?? großen Ganzen – wie das Ding praktisch notiert aus – allem – was in ein nun in der – Informatik – interessiert ist die Komplexität – in Anführungszeichen zu – nennt sich das dann die Komplexität – dieses Algorithmus – gemeint ist die – Laufzeit – wie verhält sich die Laufzeit des Algorithmus – wenn verschiedene Anzahl ein Eingabegrößen – habe was passiert wenn ich den mit zehn Sachen startet sie in Sachen Sortieren was passiert wenn ich den mit hundert tausend ?? zwei tausend – State – wie verhält sich die Laufzeit – ?? wird die Laufzeit etwa proportional – zur Anzahl sein wird sich schwächer steigen wird sie stärker steigen – Punkt – das wäre die – Laufzeit Komplexität – an das Komma letzter einfach hier mit Stoffen – in tausend ?? sind viel – Raum ich baue noch bisschen was drumrum – damit ich – verschiedene anzahlen – an Elementen ausprobieren – kann ich bei mir noch ?? Schleife drumrum vorwiegend – ähm als es dann gerne – an – wie viel Eingangsdaten – man hat wie groß die Datenmenge ist mit der man rein geht – fange gleich mal an mit – fünf Sachen sortieren – sind tausend ist ein bisschen – langweilig – ist aber maximal hundert dann am Ende – und – dass ?? sich in einer Schritten machen es soll nicht erst fünfter zehnter sechs Satiren unter dem Sortieren das ich ein bisschen langweilig – ist ?? viermal ähm mal gleich – zwei – das immer das Doppelte nimmt also Saison machen fünften – zehn zwanzig – vierzig – achtzig – in diesem Fall – das – ob ich Messwerte bestimme stellt sich physikalisches – Experiment vor dass es jetzt ein dramatisches Experiment – ich messe – gleich die Laufzeit ?? ganze Laufzeit aber so ungefähr etwas wie die Laufzeit meines Programms – für verschiedene – Größen der Eingabedatenstarter – mit Satire fünf Sachen – dann – zwei Satire zehn Sachen Satire zwanzig vierzig achtzig Sachen und komme jeweils möchte jeweils angucken – ähm – wie viel Aufwand das ist – die wächst der Aufwand – mit der Anzahl – der Eingabedaten – das ist eine ganz übliche Frage – dann – gerade mal gucken das heißt ich muss hier auch nur in – mir ich muss hier auch nur in Sachen mit Zufallszahlen – füllen – hier muss ich sagen Satire ähm davon – wenn ich sage hundert sollte eigentlich auch sagen hundert – ?? das ganz offiziell – in C plus plus würde man es was mit Kunstschreiben – in – See schreibt man jetzt was von wegen die feinen – Ressorts wie maximum number – Elements – hundert – ?? dann kann ich hier die hundert einsetzen – und hier die hundert einsetzen und wenn ich mich gleich entscheide – ich hundert als maximale Zahl zu nehmen ?? zwei hundert schreibe ich einfach die zwei hundert drei ?? und über einen ganzen Programm steht die zwei hundert ?? – so in jedem ?? automatisch durch mit fünfzehn und so weiter aber ich muss natürlich noch irgendwie erfahren was raus kommt – und er muss irgendwie mitzählen – was man streng genommen machen müsste ist tatsächlich jetzt hier die einzelnen Befehle mit zu zählen an – ihr haben wann – setzen was auf null hier vergleiche – ich die addiere ich was was auf null setzen vergleichen was addieren – noch was abziehen – ?? wir zwei vergleichen – wir was zuweisen und so weiter eigentlich müsste ich jetzt zählen wie viel Befehle ausgeführt – werden – um das bisschen aufwendig was ich tat stattdessen einfach Zähne ist – wie viel Vergleiche gemacht werden – ganz dreist bevor der Vergleich gemacht wird jährlich einfach – das ist – Pi mal Daumen eine Konstante – mal die Anzahl der einzelnen Befehle für jeden Tüv Vergleich wird es noch soundsoviel andere Befehle geben Pi mal Daumen – und weil ich faul bin zähle ich jetzt einfach nur die Zahl der Vergleich – üblicher Trick bei den Suchverfahren – merke mir das in irgend einer Variablen die Anschein kaut heißt die muss ich leider jetzt außerhalb bauen ?? – ich das so baue – ich auch noch irgendwas übergeben oder ähnliche Säuglinge sogar ganz falsch war das einfach außerhalb ?? globale Variable außerhalb – ganzjährig jeden jeweils mit Vergleiche gemacht werden Beistrich die natürlich dafür sorgen – dass ich erst mal die Zahl – auf null setzt sie jedes Mal – bevor ich das mache – und dahinter baue ich jetzt einfach ?? Ausgabe – mit der Funktion Print effektiver – Nuss am Rande hatten Pitt vermittelt – dann – das erste Saison ?? Zeichenkette – die Saat – wie ausgegeben – werden soll – das Format die Format Zeichenkette und was möchte ich ausgeben schreibe ich dahinter ?? ich möchte dieses en ausgeben – und ich möchte natürlich hier – die Anzahl ausgeht – an – dir vorne sage ich – das Format sie können einfach jede Zeichenkette angeben dann wird nur die Zeichenkette ausgegeben – und wenn sie sie irgendwo Prozent die reinschreiben – setzte diese Zahl – an diese Stelle in die Zeichenkette – und wenn sie noch mal – irgendwo – Prozent – die reinschreiben – setzte die zweite Zahl an die Zeichenkette – Komma ich bin jetzt einfach – mal Faulbach noch folgendes – soll das ausgeben – eine Zeichenkette – der ersten Stelle steht diese Zahl ähm die Größe der Eingabe – Leerzeichen – und einer Zweigstelle hoch Prozent die natürlichen – Prozente an der zweiten Stelle hier steht – einfach die gemessene Anzahl an Vergleich – und damit subsumiert sei ?? noch Zeilenumbruch – auch schon gesehen das Sonderzeichen – für Zeilenumbruch – ist Backslash in – der erzeugte Zeit dahinter noch – vor sich diese Sen hat wieder nichts damit zu tun dass er nicht der Name einer Variablen dieses Backslash N ist der Name – eines Sonderzeichens – null ein – neue Zeile – damit sind es geht brauche ich hier noch – ?? Standard ein Ausgabe glitzernder – Input Output Standard AWO in Cloud – SC Uppsala IST – das CD – Punkt – H – ich – glaube dann ist alles da wohl sein muss – Komma sondern – ich brauch das Terminal Fenster – Designausgabe – geht es Terminalfenster – die – Seele ?? tritt erst bei den Makrokontrollen – so selten vorkommt – ?? ich dann Terminalfenster – für den Chip der ?? von Auto verbaut es – die habe ich es ausgerechnet Terminalfenster – unten sollte ich eine Liste sehen – Anzahl – und Anzahl der Vergleiche – Größe der Eingabe soll ich sagen und Anzahl der Vergleich – also erscheint mir zu – mir sagen zu wollen wenn ich fünf – wenn ich fünf Sachen – in der Liste habe brauchte zwanzig Vergleich wenn ich sie in Sachen ?? ist ?? neunzig vergleiche dreiundachtzig Vergleich – weiter gucken ob ich das sie tatsächlich – eine Tabellenkalkulation – Lebendigkriege – schön – okay – Klammer zu Zusammenhang angucken – offensichtlich – ein quadratischer Zusammenhang – das sodann die üblichen Diagramme die man baut – dann – die auf der x-Achse habe ich die Größe der Eingabe – wie viele Daten sind in meinen Algorithmus reingegangen – und auf der Y-Achse – steht etwas die Laufzeit beschreibt – wie gesagt ja ich jetzt einfach gezählt wie Vergleiche gemacht werden – Beistrich müsste man sämtliche Befehle drin vorkommen aber die Zahl der Befehle wird – etwa proportional – zur Zahl – der Vergleiche sein – der Zusammenhang – sieht ganz schwer – quadratisch aus als ob hier ein Vielfaches vom Quadrat – steht – das können wir uns noch mal – der Theorie angucken – oder ein Programm angucken – warum – wird das – quadratisch werden die Anzahl der Vergleiche bauen wir die quadratisch ✂ guckt sich in der Tat an wie oft denn jetzt welcher Teil des Algorithmus – durchlaufen – wir sind die äußere for-Schleife – die wird einmal durchlaufen nur bis in minus eins – die also for-Schleife wird einmal durchlaufen – die innere for-Schleife – wird in minus eins Mal durchlaufen – an dieser Stelle komm ich also ähm mal N minus eins mal vorbei – wenn ich hier mit tausend reingehe würde ich hier tausend neun hundert neunundneunzig mal an dieser Stelle vorbeikommen – können ?? gucken ?? – so richtig verstanden haben ich gerne mal einfach den theoretischen Wert ausrechnen muss sagen okay ich würde annehmen in der Theorie das ist ähm – mal – eins weniger – okay das gut aus – sie sehen unsere Theorie fast hundertprozentig – mit der Funktion jetzt zusammen – das war ja auch einfach – diese Schleifen hier laufen – immer bis zum Ende durch ich kann – relativ einfach Vorhersagen – hat die Feinfühligkeit total billig vorhersagen wie häufig diese Schleifen ausgeführt werden – dann – aber das ganze mal bisschen – beschleunigen das ist noch nicht – wirklich geschickt man ganz minder einfachen Maßnahme – besser machen was fällt Ihnen ein wie man das verbessern könnte wenn sie sich – ihr das noch mal überlegen – Komma – ob abstrakter malen – im ersten Durchgang – im ersten Durchgang sorge ich dafür – das – alles ein Schritt weiter läuft was zu schwer ist dann kommt der – zweite Durchgang – sorge dafür das alles was – größer ist ein Schritt nach oben kommt der dritte Durchgang sorge dafür das alles was groß es ein Schritt nach oben kommt – Punkt – verdient aber was auf was man geschickter machen kann als bisher ✂ eine – billige Art das zu beschleunigen wäre folgendes kann er schon passieren das ich irgendwann jetzt – sich irgendwann jetzt zwischendurch fertig bin – mitten drin bin ich schon lange fertig – dann möchte ich – abbrechen wenn er zwischendurch schon zitiertes möchte ich jetzt nicht immer weiter immer weiter machen soll einfach sagen ?? Feierabend – jetzt herauf und ich möchte mit kriegen das er schon sortiert ist und dann nicht wieder von unten anfangen – und die Bläschen aufsteigen zu lassen das wäre mein erster Gedanke wie kann ich mit kriegen das er zwischendurch längst datiert ist ✂ Na wenn sie feststellen sind einmal durchgelaufen – auf der Suche nach Bläschen die man austauschen kann – und es ist nicht passiert – dann ist das Ding sortiert – noch andere Sachen die man machen könnte der Anfang hier scheint relativ – stabil zu sein ?? am Ende wird er ausgetauscht – aber das rustikale Vorführ wird aber nur das hier an wenn ich einmal durchgelaufen bin und ich habe nirgendwo getauscht ?? bin ich fertig dann scheint sie alle in der richtigen Reihenfolge – steht also merke ich mir – ob ich irgendwo – noch welche getauscht habe ?? eine Burschenvariable – sinnvollerweise – nun überlegen wie ich die nenne – werte ich einfach dann zu nennen – bin ich schon fertig weil das Ding sortiert ist am Anfang einer Durchsage noch nicht fertig – machen sie keine for-Schleife – mehr sondern ich sage – ?? Pfanne so lange unten an wieder noch nicht fertig bist weil – Nord – dann – Jahres ?? mit dem dann – sehen jetzt in einer Endlosschleife laufen ich setze das dann auf volkssage – solange du nicht fertig bist mach ?? weiter – das dann wird aber nie auf – Waage setzt also werde jetzt jene Endlosschleife – laufen – an – was muss ich mit dem dann machen welches bewertet sich dieses dann und wodurch das dann ✂ das dann soll mir am Ende dieses Durchgangs hier sagen nachdem das vorher durchgelaufen – ?? soll mir das dann sagen ob in diesem Durchgang noch getauscht worden ist wenn getauscht worden ist dann ist er im Zweifelsfall nicht fertig dann ist vormals – wenn nicht getauscht worden ist wenn ihr kein einziges Mal getauscht worden ist dann kann ich dann auf Drew setzen dann bin ich fertig kein einziges Mal getauscht worden – ?? unterbringen das in irgendwelchen Stellen jetzt dann auf Trude Erfolgs gesetzt wird ✂ wenn nie getauscht worden ist soll dann – auf Drew stehen dann sind fertig – wenn auch nur ein einziges Mal getauscht worden ?? soll dann auf Holz stehen ?? nicht fertig – das schreibe ich darein wenn auch nur ein einziges Mal getauscht worden ist – sind wir nicht fertig – durch vorsichtig sein ansonsten wollen wir fertig sein das heißt ich müsse jetzt obendrein sagen – bevor jetzt hier anfangen – setzen immer dann auf Thrun – sowas – solange wir nicht fertig sind läuft die äußere Schleife – zeitlich – spekulativ – ich bin fertig – und gehe dann die ganzen Vertauschung – durch und sobald eine Vertauschung wirklich ausgeführt – wird sag ich ich bin nicht fertig – das heißt es reicht eine Vertauschung hier um ihn herum in die nächste – Schleife gehen zu lassen – organisiert angucken was das gebracht hat – ?? ich mir – gerade – ob sie was falsch gemacht – ?? sehr schön – wer in C tot voll zuwendet sollte gefälligst auch Standardpool inkludieren – Wasser – verlaufen ?? das überlaufen – so – fünf sechzehn ?? vergleichen – das sind die neuen Werte zu sehen jetzt sechzehn statt zwanzig vierundfünfzig statt neunzig drei zwei drei statt drei hundert achtzig – elf siebzigster fünfundsiebzig – es ist etwas besser geworden aber letztlich rasen viel schneller geworden – auf jeden Fall hat man mit einer winzigen Änderung – dann – schon nach etwa siebzig Prozent vielleicht – ALG – siebzig Prozent der – ursprünglichen Anzahl nur noch – mit einer billigen Änderung und dass das Programm – langsamer geworden wäre – was ich hier habe – sind ja einfach jeweils Zufallszahl – des Wissing geflogen kann ich hatte mit jeweils fünf Zahlen ausprobiert – mit zehn Zahl mit zwanzig damit wird sich damit achtzig Zahlen ausprobiert – ?? diese Zahlen anders gewesen wären wenn die zum Beispiel sonst sortiert gewesen wären – das viel schneller gewesen – einer sortierten – Folge reingehen – macht dir nur den ersten Durchgang und stellt fest ist sortiert und ist fertig – als je nachdem welche Zufallszahl – regeneriert worden sind für die fünfzehn zwanzig Zahlen ist das Ergebnis ein anderes – das ganze jetzt ein bisschen seriöser zu machen – Beistrich das mit mehreren Folgen Zufallszahlen – jeweils ausprobieren – das baut jetzt noch ein – am – also – für jedes ähm – Haus jetzt obendrein noch ein – dass er mehrere Experimente – macht er Sachs mit fünf ?? mobiles – X mal aus – mit – Zähnen probier ich sechsmal aus – einem oder dass man jetzt aber er – Runde oder sowas – ?? – er – einer der dich jetzt auch gerne eine Variable dafür – und eben keine Variablennamenkonstante – dafür nennen was sie – Kunst – in und – an der Stelle kann es mit Konzert in C schreiben aber der Schirm sich an die Feinheit – ziemlich – äh konsistent – finden wir den mal – man – Klammer auf Frau uns – schreibe ich meinen Kleinbuchstaben – obwohl die in C plus plus – gerne großgeschrieben würde – und den Java – number France – abermals jedes Mal probiere ich – zehnmal aus – so zehnmal ausprobieren – nächste Runde – all das – ?? dass all das – ist innen drin – in – der Form – das ganze zehnmal – machen – was wären interessante Messergebnisse – wenn ich zehnmal – Messe – was könnte mich interessieren – ich mache meinen Versuch jetzt zehn mal jetzt – was will ich dann insgesamt ausgeben wollen ✂ ?? nicht Thema ✂ Messe ein erster Physikladen – interessiert mich der Mittelwert es wäre ?? die durchschnittliche – Laufzeit – an um mich würde auch noch der größte interessieren wie schlimm kann es maximal – werden wenn ich richtig Pech habe mit meinen Zufallszahlen – oder was nachher eben sortiert werden soll wenn ich richtig Pech haben wie schlimm kann es denn überhaupt werden – die beiden will ich bauen den größten – raus finden – und den Durchschnitt rausfinden – ?? gerade sind es geschickt macht – für den Durchschnitt brauche ich die Summe – im ?? Vermerk – ins – Deutsche – Reich bestimmt erst mal die Summe sowas erst mal ?? Summe bestimmen – so – und – für den größten – Max – nur – so – in der Summe werde ich den ganzen Kram jetzt auf summieren bin ich hier fertig bin sage ich Summe ist plus gleich – K und – die aktuelle Zahl jeweils dadrauf summieren – und angeblich ihr eben – diese Summe – durch die Anzahl – der Runden aus – jetzt weitere ganze Zahl gerundet sei so – die – Summe durch die Anzahl der Runden wäre der Durchschnittswert – den ich da habe – es möchte ich obendrein auch noch das Maximum haben – wir schon mit gepflegt – Komma hinschreiben wie die Ausgabe sein wird – ?? feuchten Knochen Prozent die davor – bereits – Zahlen – war in Thatchers dezimal ausgeben – mit Leerzeichen dazwischen – die Größe der Eingabe – den Durchschnittswerte – des Themas letztes noch Maximum – den – maximalen – Wert – das – arrangieren – ja – wie komme ich an den maximalen – Wert für die Summe summieren sich auf was mache jetzt fürs Maximum ✂ Leertaste Gruppen jeweils nach ob der neue größer ist als das bisherige – Maximum – pflegen das Maximum mit das Maxon der erstes – ersten beiden das Maxim ersten drei der ersten vier und so weiter und wenn der neue größer ist als das bisherige Maximum – Account – größer Maximum – dann müssen sich anscheinend den neuen merken – das ist dann der bisher größte – sein Maximum – bei – Account – so – okay das müsste – funktionieren – sammel jetzt also massiv Statistiken – ein – von diesem Algorithmus – sieht's dann aus – was habe ich es also gelernt wenn ich mit fünf – Zahlen zum Sortieren reingehe – brauchte im Mittel – für diese Zahlen Details gewürfelt habe braucht der Mittel vierzehn – vergleiche – aber schlimmstenfalls – zwanzig vergleiche – aber wenn ich mit zehn Zahlen reingehe brauchte im Mittel vierundsechzig vergleiche für die Zahn sie jetzt gewürfelt worden sind ?? ein stabiler Wert hier und schlimmstenfalls neunzig vergleiche – aha und was ist da passiert – in der Tat in ist zu klein in funktioniert ja ?? auf der Maschine mit sechzehn Bit so es gibt bis zwei ?? dreißig tausend noch was und wenn sie weiter zählen Hansi patzig dann minus zwei ?? dreißig tausend noch was wegen Zweierkomplement – der alte Ärger mit den Zweierkomplement – diese Zahl wird zu groß – für den Intel auf dieser Maschine – also nämlich ein lang – sinnvollerweise für alles was jetzt zählt nehme ich dafür auch ein Lok nehme man weiß ja nie – was ?? anderswo überlegen wie großes werden kann das aber schwankte es mal lang – das bleibt so – Punkt noch diese Summe hier soll ich als schlank machen – Maximum – sinnvollerweise auch als lang wenn das – hier – ein Onkel ist – okay – versus ?? bei dem Print noch sagen – ?? gucken dass der Compiler an das Compiler nett gesagt an das sowieso – der Compiler es nett und sagt das sowieso – angemessen kompatibel mit Korrespondenz vom String wieder eine sehr – schöne Fehlermeldung – er will mir sagen – diese Zahl hier Summe durch irgendwas und diese Zahl hier wechseln sie der gleich zweimal diese Zahlen – passen nicht zu Prozent D Prozent D gibt – den Thatchers aus aber keine Lokzahl das ist jetzt blank durch Inter char ist lang und das Ent misslang – der Wille ein LED haben – Langzeit dezimal ausgeben – so aber nun – okay – das sie besser aus es waren also fünf tausend irgendwas – etwas ernster – erzählt hat – uns das angucken – man – man gucken ?? wie schön der Zusammenhang oder wie schlecht der Zusammenhang – zwischen – mittlerer Dauer und maximaler – Dauer ist – Einfügen – Diagramm – sie – sehen diese Beschleunigungsmaßnahme – bringt im Endeffekt nicht viel – die – Wassermann jetzt – Orangekurve – das ist der maximale – Wert – und die blaue Kurve ist der mittlere Wert – am – Unterbeschleuniger – nicht viel gebracht in den sie gucken zwanzig neunzig drei zwei vier – zwanzig neunzig drei zwei vier – kommen – ist nicht besser geworden und wahrscheinlich ?? man die richtigen Zufallszahlen – würfelt aber auch wieder hier zwanzig – neunzig und dann nicht drei hundert zwoundvierzig – sondern wie hier drei hundert und achtzig – und – fünfzehn sechzig – statt der vierzehn zwei achtzig wenn ihr so die richtigen Zufallszahlen – auftreten ?? ich ?? genutzt zehn verschiedene ausprobiert – wenn ich das weiter ausprobieren wird dieser als Maximum worst case hat es gern dieses Maximum – wird sicherlich noch anwachsen – dann werden wir – auf dem selben Niveau sein wie vorne – das Iso die beiden – Laufzeiten – die man sich typischerweise – anguckt was ist die mittlere Laufzeit – und was ist die schlimmste Laufzeit – erfreut und – worst case – und was man angeht – ist typischerweise – nicht – jetzt direkt die konkrete Formel N mal in minus eins – oder was ähnliches hatten an sondern ich gebe das anatolische Wachstum an sich das nennt – wächst diese Kurve – quadratisch – schlimm ja kubisch – wie auch immer – also was man an gibt es folgendes – Asymptote Wachstum – ich – habe – nur nach gucken theoretisch eine Laufzeit – von – N mal N minus eins – also – ich habe eine – Laufzeit von einmal in minus eins – mal irgend eine Konstante – der sich wirklich die Anzahl der Befehle habe einmal in minus eins ist die Anzahl der Vergleiche – mit Optimierung ist etwas besser geworden und wahrscheinlich viel besser geworden – ähm – mal irgend eine Konstante um von der Anzahl der Vergleiche – auf die Anzahl der Befehle zu kommen – ?? beschreibt jetzt nur das Wachstum dieser Funktionen – sie das ausmultiplizieren – steht der ja zehnmal in Quadrat minus zehn mal in – ich beschreiben das Wachstum dieser Funktion – das heißt in diesem Fall dann groß O von – N Quadrat – so nennt sich das – mathematisch wichtige Überschreiben ist Element von – viele Leute schreiben ja gleich – an Fragezeichen zwei ganz dreisten Elements dieses groß O von ähm – irgendwas – soll eine Menge von Funktionen sein alle Funktionen – die Asymptote – Quadrat – wachsen – Asymptote – in Quadrat wachsen soll heißen – wenn sie das Verhältnis bilden – dieses – zehnmal – in Quadrat minus zehn mal en durch ein – Quadrat dass dieses Verhältnis – beschränkt bleibt – ?? funktioniert – es schlimmstenfalls – sowas wie eine Vielfalt – an die ein Vielfaches – mal in Quadrate soll das heißen Punkt – mit dieses Verhältnis bilden die Funktion durch ein Quadrat – wird es – beschränkt bleiben wenn in über alle Grenzen wächst das Komma leicht nachrechnen – sind sie mal im Quadrat durch ein Quadrat ist sie – minus zehn mal endlich ein Quadrat ist sie durch ein – das wird auf jeden Fall kleiner gleichziehen – bleiben – das bleibt beschränkt ein Quadrat über alle Grenzen – am – ?? gebe es noch – andere Klassen an Funktionen aus das es jetzt – sicherlich eine Funktion von der Klasse die höchstens so schnell wächst wie ein Quadrat – an – das wäre eine garantiert größere Klasse an Funktionen – was – in wo ist diese Funktion ja auch drin ✂ die Dachluken nicht an die Fusion aber sie haben recht das wäre garantiert – auch – in Hof und wie hoch denn wenn sie das hier – durch ihr Hochent teilen dasselbe durch ihre ?? in ein Polynom durch die hoch ähm ist das ja nicht nur beschränkt es gibt sogar gegen null das jedoch ein Wind garantiert gewinnen endlich das es garantiert in dieser Klasse auch – an – was ich jetzt dachte – ?? eigentlich ein hoch drei – wenn sie richtigen hoch drei Teilen ist es auch gerade beschränkt aber es ist nicht – es ist nichts – in der Klasse scheint es jetzt meine oben – es ist nicht – in der Klasse – Buch von N – das ist nicht in der linearen Klasse das wächst stärker als Lin ja wenn sich unten nur durch Entteil – steht hier zehnmal ähm das ganze nicht beschränkt – ?? in der Klasse ist es nicht das es in der Klasse – der Funktionen die – Asymptote quadratisch wachsen – oder langsamer nicht in der Klasse die Asymptote stehen ja wachsen oder langsamer – mit dieser O von groß O von irgendwas Notation – schlecht man sich dann an dieser Stelle – bei den Algorithmen von morgens bis abends rum – zu welcher Klasse von Algorithmen gehört dieser Algorithmus der gehört zu – dieser Klasse von Algorithmen und deshalb gehörte automatisch – zu dieser Klasse von Algorithmen mit N hoch drei und N noch zweiundvierzig – deshalb hat gerade automatische – Klasse von Algorithmen mit EVN – diese ?? wirklich super langsam – das – ist eine Abstraktion der Laufzeit – man guckt sich nicht an wie viel Sekunden läuft das Ding oder – eigentlich auch nicht mehr wie viel Befehle – muss der Prozessor ausführen sondern sich ganz abstrakt an wie diese Laufzeit – wächst – wenn ich – die Anzahl meiner Eingabe die Größe meiner Eingabe verzehnfachen – wie dieser Algorithmus – im Endeffekt – die Laufzeit – höchstens für hundert fachen und wenn ich meine Eingabegröße – vor hundertfache – wird dieser Algorithmus dann die Laufzeit – im Endeffekt höchstens vierzehn tausend fachen das ist der Gedanke im Hintergrund – ist dann nicht hundertprozentig – das was dann auch herauskommt Komma dass der Gedanke im Hintergrund – wenn ich meine – Eingaben groß umso soviel ändere was wird passieren mit der Laufzeit des Algorithmus – das ?? damit mit Weg dargestellt Asymptote ich für sehr große N man weiß nicht was für kleine en passiert – was das Ganze so bisschen zweifelhaft – macht die theoretischen Informatiker – beschäftigen sich hier dann eben Jahre mit solchen Abschätzungen – über Laufzeiten – aber – es kann sein dass das in der Praxis – völlig irrelevant ist was sie da produzieren – die Can haben dass ein Algorithmus – quadratische Laufzeit hat – das Verzeichnis nicht mehr so weltweit – zu – haben und dieses hier – quadratisch – hochgeht – dass dieser Algorithmus wovon im Quadrat ist weil das jeder zum Schluss maximale Parabel wird – in – kann ihn aber passieren das in Algorithmus haben der scheinbar schlechter ist – O von – E hoch N das wäre – super schlecht normalerweise – aber der Algorithmus mit wovon Eogent kann im wahren Leben so eine Laufzeit haben – dass der für alle anzahlen die interessant sind – Beistrich dass von N gleich null bis N gleich eine Million immer noch besser ist als der – theoretische Untersuchung – über dieses symbolische Wachstum – muss man mit sehr viel Körnchen Salz genießen es kann sein dass ein Algorithmus der auf dem Papier super schlecht aussieht – in der Warenwelt – schneller ist als ein Algorithmus der auf dem Papier – Komma besser aussieht in Quadrat wäre nicht gut aber sehr zumindest besser auf aus auf dem Papier – weil – der Unterschied zwischen diesen beiden Funktionen – dass die ganz flach anfängt und dann explodiert – einfach von diesem – groß O – nicht erfasst wird – also Vorsicht eine Stelle – typischerweise – Komma mit diesen Abschätzungen was anfangen aber man muss sie – mit einem Körnchen Salz nehmen – so – das wäre unser Standardalgorithmus – jetzt hier gewesen – Bubblesort – netterweise – ist in den meisten Bibliotheken – eine – Sortierfunktion – eingebaut – also bevor sie anfangen sowas selbst zu programmieren – und dabei etwas bauen das dann sehr langsam wird im Zweifelsfall oder – was sogar fehlerhaft ist benutzen Sie das was eingebaut – ist nicht Zeichen ist im Verhältnis – dazu was die eingebaute Funktion kann – die nennt sich – NC – Q sorgt – was an Quicksort erinnern soll es ist im Standard nicht festgelegt das Essen Quicksort sein muss Punkt es wäre keine dumme Wahl dafür – ?? man weiß aus dem C Standard nur wie sich die Funktion von außen verhält nicht – wie sie in gebautes auch wenn sie Grußwort heißt – unser Absatz Akkus sorgt Quicksort – soll das sagen aber wie gesagt – weiß ich was drin steckt sie heißt einfach Grußwort – an und ist auch hier in der – Standard App definiert – an – diesem Quicksort – gebe ich auch wieder des Gräber sortiert werden soll Komma – ich gebe ihm wieder die Anzahl – der Elemente – die in diesem ?? stehen zum Sortieren – jetzt wissen wir sind Regie – solche Bibliotheksfunktion – sind dazu gedacht – mit allem möglichen Krempel zurechtzukommen – diese Bibliotheksfunktion – soll – Interesse Tieren können Sie soll Zeichenketten sortieren können Sie soll – er Warenkörbe – Sortieren können Sie soll Telefonnummern – Einträge sortieren können alles mögliche sollte Sortieren können – das ungeschickte ist – dass sie erstens nicht weiß wie groß ein Datensatz ist ich sage hier was das Gerät ist und wie viel drin stehen – muss er noch sagen wie groß das ist das ist das dritte Argument – und dann muss ich auch noch sagen wie denn – zwei – Telefonnummern – verglichen werden oder wie zwei Zeichenketten verglichen werden oder wie zwei – Warenkörbe verglichen werden das kann sie ja wirklich wissen dafür sind diese bei mir nötig das habe ich über mein Bubblesort eingebaut – der weiß das sind – bitte etwas – an der weiß in der das vergleiche bei dieser allgemeinen Quicksort Funktion muss ich das einsacken erst mal – die groß die einzelnen Datensätze sind in diesem Essays stehen dafür gezielt wieder das Zeiss auf – seinen Fall natürlich von ihm – was auf dieser Maschine einfach zwei ist ein in der Maschine zwei Beistrich sechzehn Bit könnte auch zwei reinschreiben – aber dann wird es von einem Prozessor kompilieren zum Beispiel den Pentium kombinieren Verstärkungen – deutlich mehr sicher zwei sechsundvierzig wir sind – das ist die sichere Wahl scheint da nichts weiter anderen Schreibens rein die Größe eines in den beiden stimmt es auf jeden Fall – an und die hinten ersetzt – überraschend – muss ich sagen werde zwei vergleichen kann ich kann ihm hier alles mögliche für die Füße werfen an Elementen – nicht nur ganze Zahlen – aber zum Ausgleich muss ich denn sagen wir zwei davon vergleichen soll rechnen die Funktion – nicht als Übergeber zu vergleichen mal Fachkomper – geben ihm eine Funktion – diese Kriegs der Quicksort Algorithmus ruft diese Funktion auf – Wasser mein Praktikum ja schon mal dass das System – ihre Funktion aufruft – und das wieder vor – Quicksort – ruft meine Funktion auf Vergleich damit zwei Einträge ich weiß selbst hoffentlich wie zwei Einträge vergleichen – ?? kommt – auch ist eine Funktion – vor – ?? davor eine Funktion die jetzt kommt der Nenner – können sie auch – keinen dann schreiben Sie unten kahl und schreiben darum auch Karl – an – und der C Standard gibt vor wie diese Funktion aussehen muss damit funktioniert – und zwar – gibt sie eine ganze Zahl zurück – und sie kriecht zwei Sachen übergeben – ?? schreibt das erst mal so – ein – Sekundärfunktion – Beistrich zwei Sachen und soll mit einer ganzen Zahl sagen – die sie dann zurückgeht wenn man es möchte mich finde – da ist es – dann – so mit einer ganzen Zahl sagen – ob der vordere größer ist als der hintere – ob der vordere gleicht im hinteren ist ?? der hintere größere Satz erfordere – am – der Algorithmus gibt den ?? zwei zum Vergleichen – das sieht jetzt bisschen Bild aus Kunst – Voith – Sternchen – X der eine zu vergleichen und der andere Kreuztransportsternchen – Y der andere zum vergleichen – dann auf dieses Wollsternchen – will ich an dich gar nicht so viel eingehen – bisschen abgedreht – haben – ansatzweise was das bedeutet was er ihnen gibt ist die Hausnummer – eines Dings im speichererweise – noch gar nicht was da steht stehender Kundennummer anstehender – Eurobeträge – Ständer in der Zeichenkette – die Filterfunktion – weiß nicht was da steht im Speicher was ihn gibt – ist ein Zeiger auf irgendwas im Speicher das es sowas Wollsternchen – ist ein Zeiger auf irgendwas – Voith kennen wir als – am – ich lasse einen – ich gebe kein Parameter für ?? Funktion würde ich gebe nichts zurück an dieser Stelle heißt es – ein Zeiger auf irgendwas dieses X ist ein Zeiger auf irgendwas – das System weiß nicht worauf es Zeichen – und das was da steht was ich nicht anders ?? dieses Konzept der Werte an der Stelle steht wird unverändert gelassen – an – das ICD – ignorieren ich kriege zwei Sachen die ich vergleichen soll das ist der Gedanke dahinter – mit so kommt der Funktion soll ich jetzt sagen ob der eine größer ist dann der größer ist beide gleich sind in welcher Reihenfolge stehen sollte eine zuerst eine ZUERST – oder Circa zwei gleich sind – Komma kleine technische Tricks muss er wieder auf meine ganzen Zahlen kommen – hier habe ich Anzeige auf irgendwas – X ist ein Zeiger auf irgendwas – am – den verwandle ich in ein Zeiger auf ein Kind weil ich weiß das in meiner Liste – in den Schuss stehen kann ich das machen und dann nehme ich diesen Zeiger auf ein Kind und holte den Wert raus – wenn das – Totalgleis – künstlerische laut Medien begeht tizian – heute um die – Laufzeit und nicht um die technischen Tricks hier mit X – als ich wohl aus dem ersten den echten Wert raus und ich wohl aus dem zweiten den echten Wert raus – und Sekundärfunktion – soll jetzt – melden – ob der erste größer ist oder der zweite größer ist oder beide gleich sind wenn der erste größer ist – stets einem Standard wenn der erste größer ist als der zweite – solche kommt der Funktion eine positive Zahl zurückgeben – größer ist als der zweite – gebe eine positive Zahl zurück sinnvollerweise – nur eins dümmste positive Zahl – wenn – ordentlich kann es wegen des Returns aber schon aus – wenn die beiden gleich sind – ewig – null zurück – das sagt der Standard – die Reihenfolge egal ist Beistrich leicht über Null zurück – und ansonsten – gebe eine negative Zahl zurück ?? ist der zweite größer gewesen – zu – was – ist an Dortmunds Sackrhythmus – der Vorgang – gegeben ist aber der Quicksort Algorithmus ruft meine Funktion auf wenn immer was zu vergleichen ist oder meine Funktion auf – Punkt – ich kann in die Liste geben sah gemäß den sechs Stück in der Liste ich sag ihm jedes davon ist zwei Bytes lang und ich sagen wie zwei davon verglichen werden sollen – ist das komplett abstrahierte nimmt sich der Algorithmus einfach noch was da in jeglichen Witz steht – und schiebt das durch die Gegend muss nicht wissen dass das Zahlen sind oder Telefonnummern – ganz losgelöst vereinbar sei konkret steht – Diskussion ?? besonders auch noch – mit selbst Discount hier – also bei jedem Aufruf – der oben rein bei jedem Aufruf soll mit Zellen im ?? ins Vergleichen – mitgezählt und jetzt ?? ich eben auch jedes Vergleichen mit – Komma das ganze – am – Mal in Relation setzen zu dem Bubblesort – ist dasselbe mit dem eingebauten Vergleich – ?? gucken ob der eingebaute Vergleich ?? wirklich funktioniert – kann ich Herrn – das man dann weg weiter vor – und gucken ob das hinhaut – so bevor der ausgeführt – ist steht da – eine Folge von fünf Zufallszahlen – zu rufe ich die Funktion auf – wunderschön und sie hat mir – sortiert von kleiner groß wie sich das gehört also scheint soweit zu funktionieren – weg und wieder raus und lass sie nur bis zu Ende laufen – so – das hat er jetzt an Messwerten wenn Sie wollen – für die eingebaute Funktion – muss meine zusammen – schreibt das mal – vor Ecke das war unser Bubblesort noch – und nun der eingebaute – Kursortzeichen – das angucken der unten hatte ich – maximal – fünf tausend sieben hundert irgendwas und der Bubblesort kommt hiermit – maximal acht hundert wenn er – achtzig sortiert es also – um Klassen besser schmeißt das man in ein Diagramm vielleicht – dann – ?? das hier ist Babel Mittelwert gewesen – gehört das hier war – Bärbel – worst case – PCs mit – Macs – hören – Sie mit dem Fuß sorgt – Mittelwert – wird für den soll – und wir nehmen mal den Macs für den Kursort – vergessen – und das jetzt in – Köln einfügenden – Diagramm – Y – okay – so sieht's aus – ?? – an sie sehen auch bei diesen – Quicksort – scheint muss ich sagen – scheint das Maximum – Max vergessen bei diesem Quicksort scheint das Maximum – nicht weit über dem Mittelwert zu liegender Musik ?? noch was sagen – Punkt der Eindruck täuscht – Senke davon ab was für Zufallszahlmann – reingeschmissen hat mit den üblichen Zufallszahlen – muss man sehr viele Werte ausprobieren wirklich auf den schlimmsten Wert zu kommen für den groß ?? – ähm was mit ihr etwas ablesen kann ist der älteste groß Ort relativ stabil – Schweiz weit weit unter dem Bubblesort bleibt – an – die Form dieser Kurve kann man jetzt noch nicht ganz erkennen – Komma müsste viel mehr Datensätze nehmen – das scheint erstmalig im Jahr zu sein noch ein bisschen weiter baut sieht man das es nicht genial das nimmt schon leichten Knick nach oben – aber nicht so ganz so stark wie X Quadrat – an das groß Kanal für den Quicksort überlegen wenn es in ein Quicksort ist ?? ich weiß läuft – etwas laut Standard nicht das diese Funktion eingebaut ?? zum Kuh soll wirklich ein Quicksort ist sie heißt traditionellerweise – so – wenn sie einer wäre – kann man sich überlegen – wieder das Laufzeitverhalten – sein muss Bubblesort ?? muss im Quadrat überlegt – man im Gussort – Quicksort mit seiner ist Komma nicht auch noch überlegen – am – Quicksort – hat folgenden – Gedanken – ich – nehme mir die Elemente die – sortiert werden sollen – ernenne einen davon zum – Dreh und Angelpunkt – ?? wird welchen auch immer man kann sich irgend einen aussuchen – gute Strategie ist wirklich zufällig einzunehmen – man kann auch einfach den letzten nehmen – den ehernen Mann – zum Dreh und Angelpunkt – ?? wird – Komma – und unser – ?? sorgt man dafür durch Vertauschung – dass alle die größer sind – rechts von dem einsortiert werden – von den verwirrt einsortiert werden – und dass alle die kleiner sind – links davon einsortiert werden das kriegt man mit einfachen Vertauschung – hin – was ich damit im ersten Schritt auf jeden Fall erreicht habe ist das alle Zahlen kleiner als dieser ?? und ?? Punkt – links stehen alle Zahlen größere ?? von rechts stehen – das heißt – der JEDE steht schon an der richtigen Stelle – es kann sein das hier noch mal umgetauscht werden muss eine kleine Anzahl dastehen und wenn ihr alle größeren Zahl dastehen Beistrich kann es hier noch mal umgetauscht werden soll Beistrich – an – die vor dieser – das sein Wirrwarr – zweiundvierzig – und hier habe ich was trennen wie dreizehn – und achtundneunzig – und siebzehn – und sieben – ?? – für den ersten Schritt erreicht werden dass die achtundneunzig – auf der Seite steht und dass die sieben und die siebzehn und – die dreizehn auf der Seite stehen – ?? es ist nicht gewährleistet – dass die in der richtigen Reihenfolge stehen nur dass die Gans nur alle die kleiner sind als diese zwoundvierzig Klicks davon stehen an die größer sind rechts davon stehen sich einfach durch vertauschen hin und ich kann mir zwei Schwankungen der links davon ist der größer als zwoundvierzig dann verdaulich die beiden – Städte schon mal auf deiner Seite der Google wieder den links davon an an – Sehende würde jetzt nicht alle mit kriegen die dahin noch stehen und wissen raffinierter – angehen will ich es aber gar nicht vorführen das riecht man relativ billigen – Anteil sie nach links alle die größer sind nach rechts und dann macht man das ganze – noch mal – Teile und herrsche dessen übliches Prinzip – bei den Algorithmen – man sucht sich hier ein – solches Verwirrtelement – und macht das ganze noch mal – alle die kleiner sind als das – auf die linke Seite alle die klar größer sind als das auf die rechte Seite – das macht man hier noch mal – das macht man hier nochmals immer wieder immer wieder bis man fertig ist – dass sie total kompliziert aus man kann sich auch höllisch verprogrammieren – Komma das baut – aber das wird – schneller werden – als der Bubblesort das ist ein wesentlich intelligenteres – ist der Bubblesort – könnte sich mal grob ?? muss man gut überlegen – wie viel Vergleiche man braucht die Anzahl der Vergleiche Anzahl – Vergleich – um das hier zu sortieren – ich habe ähm Elemente – vergleiche – hier mit dem letzten Ende jedes davon Vergleich mit dem letzten – die die kleines N Chips erforderliche Größe sind schräg nach hinten das heißt hier habe ich im Endeffekt ungefähr – ein Vergleich eigentlich nicht Ent sondern ein weniger – das macht für groß N jetzt keinen großen Unterschied – im nächsten Schritt – mit jetzt hier aufteilen – und hierum noch mal aufteilen – zumal das Upgrade aussieht so – um noch mal auf der diese Vergleiche brauchen sich ihr ✂ sie wirklich in der Mitte aufgeteilt – ist – wäre das sie ungefähr in Halbe – sie müssen in halbe Sachen mit dem ein Pivotelement – wird – Englisch in ein Quit Element vergleichen – und hier müssen Sie nochmals etwa ein halber – mit dem Eintritt Element vergleichen – in Halle plus innerhalb sind wieder ungefähr ein – ?? des jetzt noch ein zweiter treibt – wenn es sie gleichmäßig aufgeteilt wäre das in Viertel in Viertelfettliste – müsste hier etwa ein Viertel – vergleichen – mit dem Wirtelement – noch mein Viertel mit dem David Element noch mal nochmals jemand entwickelt ist schon wieder ähm – in jeder Generation – sozusagen – das – ungefähr ein vergleiche – wie viele von diesen Generationen – habe ich ungefähr – ich höre auf zu sortieren wenn hier und nur noch ein einziges Element jeweils steht – ?? dann brauche ich nicht mehr – links und rechts zu schieben – Punkt die Frage ist als im Endeffekt bin ich in Elemente gegeben habe wie häufig ich durch zwei teilen kann Pi mal Daumen durch zwei teilen kann dass sich in der Mitte liegen – aber – im Mittel – wird es ungefähr in der Mitte liegen an – wie häufig kann ich fortlaufend durch zwei teilen wir sind zwei Elemente Darwins vier Teile da sind's acht Teile sechzehn Teile zum Schluss ist das dann einfach der zweier Logarithmus ?? Komma Fanblock – Block zwei – Punkt zwei von ähm – Generationen – so viel schichten werde ich hier untereinander haben – wie oft ich durch zwei Tage – wenn sie um – zweiunddreißig – sind ?? vielleicht – fünf von den Generation mit vierundsechzig sind brauche ich ungefähr sechs von diesen Generation – Rhythmus zwei von ?? und dann komme ich – Pi mal Daumen ?? natürlich keine seriöse Herleitung aber die mal Daumen komme ich dann drauf – okay das Ding wird einmal – zwei ?? Rhythmus aus N vergleiche – benötigen – also würde ich vermuten – ?? Vermutung – im Mittel – zur – ähm mal den zweier Logarithmus – aus N vergleiche – das – würde ich vermuten – da können sich die Informatiker natürlich dann – ganze Woche lang beschäftigen das sauber herzuleiten – aber – Sommer schon eine Hausnummer – ?? jetzt mal ganz frech daneben schreiben was heißt das – um – dort – Max war das – dann – unsere banale Theorie – wäre also das ist – die Zahl ähm – mal den zweier Logarithmusloklok – vorhanden – ähm – sind zwei – das – wäre unsere banale Theorie – interessiert sich völlig abwegig – für so etwas was man aus der Tasche zieht sich nicht ganz so falsch aus statt sechs hundert achtundsechzig – gemessen – täglich fünf hundert und sechs raus statt hundert zehn gemessen sechsundachtzig – gemessen für irgendwas Wochenende weder – aus der Tasche zieht eine schlechte Idee – der Quicksort – ist von dieser Klasse – N mal – locker ähm so schreibt man das dann auch was es nicht von der Klasse O in – der ist nicht genial – sondern etwas schlecht aber ist nicht viel schlechter ist besser als ein Quadratslogarithmus – ist ja eine langsam wachsende Funktion – N Lok N ist irgendwo zwischen Quadrat – und der geraden – Arm auf halben Wege dazwischen – wird der – dieser Quicksort mit seiner Laufzeit in lockerer das ist auch das übliche Verhalten für gute – Suchverfahren – der – Bubblesort – wächst mit dem Quadrat – im Mittel – der Quicksort wächst mit entlocken – würde das ganz genau anguckt das ihm gesagt im Mittel – muss ich eigentlich auch noch angucken wie schlimm es den maximal werden kann – und die Zahlen hier trügen – wenn ich wirklich – gut verlesene – Zufallszahlen – habe – extrem schlecht fallen – wenn wir das hier auch wieder quadratisch werden das ist das komische beim Quicksort ist im Mittel – entlockt ähm – relativ schnell aber wenn ich richtig Pech habe mit den Zufallszahlen – oder mit Wasser Komma ich sortiere mir das quadratisch werden sie sehen mit dem Paar zu Fall zeitliche gezogen haben wird es nie so schlecht – muss wirklich sehr lange ziehen bis man den ganz schlechten Fall erwischt der ganz schlechte Fall wäre – das er – hier immer einen einzigen zur Seite stellt – Beistrich ganz alleine und dieses hier gibt's gar nicht der steht weiterhin der ganz auf der Seite Unterschiede da wieder ganz auf der Seite brauche ich etwa schlossen sich in Durchgänge und jeweils außerplanmäßig – ein Vergleich und ich hab wieder was von O zwei – also der worst case – bei dem – in – der worst case – bei dem es tatsächlich wovon im Quadrat – aber das was ein typischerweise interessiert ist richtig schnell und dass er in der Praxis – und deshalb ist dieser Algorithmus eingebaut – mit den typischen – Fällen – ist der – super schnell und relativ einfach zu behandeln