Eine Einführung in Algorithmen in Python | Herman M. | Skillshare

Playback-Geschwindigkeit


  • 0.5x
  • 1x (normal)
  • 1.25x
  • 1.5x
  • 2x

Eine Einführung in Algorithmen in Python

teacher avatar Herman M., Enthusiastic video game developer and creator

Schau dir diesen Kurs und Tausende anderer Kurse an

Erhalte unbegrenzten Zugang zu jedem Kurs
Lerne von Branchenführern, Ikonen und erfahrenen Experten
Eine Vielzahl von Themen, wie Illustration, Design, Fotografie, Animation und mehr

Schau dir diesen Kurs und Tausende anderer Kurse an

Erhalte unbegrenzten Zugang zu jedem Kurs
Lerne von Branchenführern, Ikonen und erfahrenen Experten
Eine Vielzahl von Themen, wie Illustration, Design, Fotografie, Animation und mehr

Einheiten dieses Kurses

6 Einheiten (43 Min.)
    • 1. Einführung

      2:06
    • 2. Computational Komplexität

      5:24
    • 3. Bubble

      9:01
    • 4. Sortierung

      6:59
    • 5. Sorte zusammenführen

      11:09
    • 6. Schnelle Sortierung

      8:44
  • --
  • Anfänger-Niveau
  • Fortgeschrittenes Niveau
  • Fortgeschrittenes Niveau
  • Alle Niveaus

Von der Community generiert

Das Niveau wird anhand der mehrheitlichen Meinung der Teilnehmer:innen bestimmt, die diesen Kurs bewertet haben. Bis das Feedback von mindestens 5 Teilnehmer:innen eingegangen ist, wird die Empfehlung der Kursleiter:innen angezeigt.

806

Teilnehmer:innen

--

Projekte

Über diesen Kurs

fdccbcfe

Dieser Kurs in Algorithmen ist ein umfassender Start in die schöne Welt der Informatik Dieser Kurs bereitet dich auf einen tollen Job in einem technischen Feld vor und ist ein wesentlicher Schrittstein für das Vertiefen in Datenstrukturen und Algorithmen und Programmierung im allgemeinen.

In diesem Kurs werden wir uns ansehen, wie computational Komplexität und deren Bedeutung ist, gefolgt von 4 der grundlegenden Sortieralgorithmen is, is, Zusammenfügung und sort, durch Visualisierung und Demonstration in Python.

Der gesamte Kurs ist einfach zu verstehen und relevant für die reale Anwendung in der Welt.

Triff deine:n Kursleiter:in

Teacher Profile Image

Herman M.

Enthusiastic video game developer and creator

Kursleiter:in

I am an enthusiastic programer, video-game developer and creator. I've been working as a programmer and designer for a number of years now, building all kinds of things from small mobile games to fully immersive VR experiences.

I used to work in web and application development for big and small companies, building e-Commerce systems and websites. This was until I found game development and teaching hit the spot for me.

I have a passion for creation and a knack for teaching (both my parents and grandparents were teachers).

Vollständiges Profil ansehen

Kursbewertungen

Erwartungen erfüllt?
    Voll und ganz!
  • 0%
  • Ja
  • 0%
  • Teils teils
  • 0%
  • Eher nicht
  • 0%
Bewertungsarchiv

Im Oktober 2018 haben wir unser Bewertungssystem aktualisiert, um das Verfahren unserer Feedback-Erhebung zu verbessern. Nachfolgend die Bewertungen, die vor diesem Update verfasst wurden.

Warum lohnt sich eine Mitgliedschaft bei Skillshare?

Nimm an prämierten Skillshare Original-Kursen teil

Jeder Kurs setzt sich aus kurzen Einheiten und praktischen Übungsprojekten zusammen

Mit deiner Mitgliedschaft unterstützt du die Kursleiter:innen bei Skillshare

Lerne von überall aus

Ob auf dem Weg zur Arbeit, zur Uni oder im Flieger - streame oder lade Kurse herunter mit der Skillshare-App und lerne, wo auch immer du möchtest.

Transkripte

1. Einführung: Guten Tag, Damen und Herren auf Willkommen zu diesem Video Wahlen Siris über eine Einführung in Algorithmen in Python. Mein Name ist Harmon. Ich bin Videospiel-Designer und Entwickler, die derzeit bei Sea Monster Entertainment in Kapstadt, Südafrika,tätig Kapstadt, Südafrika, sind. Ich arbeite schon seit einiger Zeit in der I-T-Branche. Früher baute ich riesige E-Commerce-Systeme, fand aber heraus, dass das Spieldesign mehr nach meinem Geschmack war. Und ich genieße es, zu unterrichten. Ich studierte Informatik und Multimedia an der Universität Pretoria und war schon immer fasziniert davon, wie Algorithmen an den brillanten Köpfen hinter diesen Datenstrukturen und Algorithmen arbeiten . In dieser Videoserie werden wir einen Blick auf Sortieralgorithmen werfen speziell. Warum sollten Sie Sourcing-Algorithmen lernen? Sie sind also ein großartiger Ort, um beim Lernen von Algorithmen zu beginnen. So können Sie sagen,, Warum sollten Sie so Einzelzimmer lernen, Sie sind bereits in vielen Programmiersprachen enthalten. Nun, das stimmt, äh, äh, Python Say zum Beispiel hat zum Beispielden Tim verkauften Algorithmus. Dies ist eher eine akademische Übung. Teoh, gib dir einen Fuß in die Tür, wie Albertans funktionieren. Es gibt einer Person mehr Einblick in die Funktionsweise dieser Systeme bei ihrer Relevanz für Probleme der realen Welt. Und schließlich ist es, weil sie ziemlich braucht sie. Sehr cool. Zuerst lernen wir die Rechenkomplexität und die Effizienz von Algorithmen kennen. Dann werden wir die grundlegendste Quelle machen, diese Blasen-Sortierung. Dann die Einfüge-Sortierung. Danach werden wir einen Blick auf meinen persönlichen Favoriten werfen, die Merge-Sorte und schließlich die halb entsprechend benannte Quick Sort. Jede Lektion ist in eine Beschreibung unterteilt, eine Aufschlüsselung der Komplexität des Oliver, sie besten Durchschnitt und schlimmsten Fall. Dann nehmen wir einen Blick auf eine Visualisierung von Halabi Funktion führt, gefolgt von einem Eintauchen in Codierung, dass Algorithmus Onda. Wir werden das alles einschließen, indem wir eine Visualisierung einen Gewinn machen, da Sie dann wissen, was hinter dem Vorhang vor sich geht . Dies ist für Studenten, die sich für Algorithmen über die Feinheiten der Informatik interessieren . Ob Sie gerade erst anfangen oder alten Hut sind, es wird etwas in diesem Video Wahl Siris für Sie 2. Computational Komplexität: Guten Tag, meine Damen und Herren, und willkommen zu dieser Lektion über Big O über Rechenkomplexität. Der Grund, warum wir größere und Rechenkomplexität lernen müssen, liegt darin , dass wir die Effizienz anhand der von uns verwendeten Algorithmen messen. Daher ist es sehr wichtig in der Informatik und speziell beleidigenden Algorithmen zu definieren was ein gutes oder ein schlechtes über sie ist. Die Big O-Notation wird in der Informatik verwendet, um die Leistung oder Komplexität zu beschreiben. Oft hat Algorithmus Big oh speziell das Worst-Case-Szenario beschrieben, aber es kann verwendet werden, um die erforderliche Ausführungszeit oder den Speicherplatz zu beschreiben, der entweder im Speicher oder auf der Festplatte vom Algorithmus verwendet wird , speziell mit Sortieralgorithmen. Wir können es auch verwenden, um einen durchschnittlichen Fall oder ein Best Case-Szenario zu beschreiben, da Sortieralgorithmen einen durchschnittlichen schlimmsten oder besten Fall vorsortierten Zustand haben können. Was ich damit meine, ist, wenn wir ein Array von fünf Zahlen haben, das ist 38216, das völlig ungesalzen ist, richtig? Aber es ist nicht vollständig in umgekehrter Reihenfolge, was bedeutet, dass es ein durchschnittliches Fallszenario wäre. schlimmste Szenario wäre, wenn es 54321 wäre. Der Grund, warum das schlimmer wäre, ist, weil der Algorithmus das gesamte Array tatsächlich umkehrt. Das wäre also das schlimmste Szenario. Fort Best Case-Szenario wäre 12345, was bedeutet, dass die Arrays tatsächlich bereits sortiert , und wir überprüfen nur, um zu sehen, dass es ist. Als Programmierer fand ich den besten Weg, Big 0 30 zu verstehen, ist durch Code, und wir werden das während des gesamten Kurses tun. Was ich tun werde, ist Ihnen die verschiedenen Zustände zu beschreiben. Sie werden sehen, dass sie hier in der ersten haben wir 01 Also niemand beschreibt einen Algorithmus , der immer in der gleichen Zeit oder Raum ausgeführt wird, unabhängig von der Größe der Importdaten. Das ist also extrem effizient. Es ist erstaunlich, Andi, es gibt sehr, sehr wenige, die alte Räume sortieren, die tatsächlich an einem abziehen können. Dann haben wir Oh, und so beschreibt O N einen alten Rhythmus, dessen Leistung linear in direktem Verhältnis zur Größe des Eingangsdatensatzes wachsen wird . Was ich damit meine, ist, wenn wir ein Array von 20 Gegenständen haben, richtig? Wenn wir ein weiteres Eis hinzufügen, wird die für diesen Isil erforderliche Verarbeitung nur linear wachsen. Während, wie wir später sehen werden, mit Owen quadriert, es exponentiell wächst. Das wird also in diesem Handwerk dargestellt, das wir im Gelb hören, ist, dass, wenn mehr Daten hinzugefügt werden, wenn in diesem Fall mit einer Rate, die Rechenkomplexität davon linear zunimmt. Ich werde zu Logarithmen wie N log end, Andi Log und Nana kommen. Aber zuerst, lasst uns durch 20 und Tintenfisch gehen. Owen squared stellt also einen Algorithmus dar, dessen Leistung direkt proportional zum Quadrat von der Größe des Eingabedatensatzes ist. Dies ist also üblich bei Algorithmen, bei denen verschachtelte Inspirationen über den Datensatz involviert sind. Tiefergehende Nachrichten. Rationen werden in O. M. zur Macht von drei oder o Ende zu den mächtigen etcetera, etcetera, etc. führen M. zur Macht von drei oder o Ende zu den mächtigen etcetera, etcetera, . Das ist also sehr ineffizient. Reaktion will sich wirklich davon fernhalten. Also hier drüben können wir sehen, oh, und quadratisch in diesen in diesem Video, Siri ist, wo das die schlimmste Rechenkomplexität ist, die wir sehen werden. Wir werden 02 bis zur Macht des Endes überhaupt nicht sehen, denn um ganz ehrlich zu sein, wenn das Sortieren so ineffizient ist, benutzen wir es einfach nicht. Wir studieren es nicht einmal. Lassen Sie uns über das Ende sprechen. Es bezeichnet einen alten Rhythmus, dessen Wachstum sich mit jeder Ergänzung zu den Eingängen verdoppelt. Datensatz. Die Wachstumskurve von 02 bis zur Leistung und Funktion ist exponentiell, beginnend mit einem sehr flachen und steigenden meteorischen Lee. Werfen wir einen Blick auf Logarithmen, so dass Logarithmen etwas schwieriger sind, zu erklären. So alte log n bezieht sich auf eine Funktion oder älter sie oder Schritt überall über sie, arbeiten in einer Menge Zeit proportional zu dem Liebhaber der Regel eine Basis in den meisten Fällen und alle Beispiele, die wir in der Zukunft sehen werden. Die häufigsten Attribute einer logarithmischen Laufzeitfunktionen sind also, dass die Wahl des nächsten Elements, auf dem einige Aktionen ausgeführt werden sollen, eine von mehreren Möglichkeiten ist. Andi wird wieder nur und nur eine muss ausgewählt werden oder die Elemente, auf denen die Aktion ausgeführt wird, sind Ziffern aus. Also 00 log Feind hier ist lächerlich effizient, nicht so effizient wie 01, aber sicherlich effizienter als die lineare o n. Und dann oh, und schauen, und es ist eigentlich ziemlich große Reichweite hier drüben. Aber es ist immer noch eine bessere Rechenkomplexität als sagen, Oh, und quadriert. nächsten Videos werden wir uns viel tiefer mit diesem Konzept beschäftigen. Bleiben Sie dafür herum. 3. Bubble: Hallo, meine Damen und Herren, und willkommen zu dieser Lektion über die Blase Sorte. Also lasst uns da reinspringen. Was ist die Blase Sortierung? Nun, die Blase Quellen eine der grundlegendsten Beschaffung eines Logarithms Ondas, die einfachste zu verstehen, weshalb wir hier beginnen werden. Es sind grundlegende Ideen, die größten oder die kleinsten Elemente aufzublasen, je nachdem, ob Sie sortieren oder Reverse-Sourcing in der zweitgrößten in der dritten und so weiter. Es ist derjenige bis zum Ende der Liste. Jedes Element nimmt einen vollständigen Sweep durch die Liste, um sich an seiner richtigen Stelle zu finden, Also die Ball-Sourcing ist ein schrecklich ineffizienter Algorithmus. Andi Leute fragen Warum, warum Sie die Blase sortieren lernen, wenn bereits Programmiersprachen wie Python bereits Essen. Hervorragende Sortierung ältere wie Tim sortieren auf. Das ist erledigt. Maura ist eine akademische Übung, um die Grundprinzipien des Sortierens nicht zu vergessen. Also die Kugelquellen, sagte ich schrecklich, schrecklich ineffizient, mit einer schlimmsten und durchschnittlichen Fallkomplexität aus oh, und quadriert, was die Mawr-Elemente bedeutet, die dem Array hinzugefügt werden. Der Verstoß gegen die Bearbeitungszeit stieg exponentiell an. Interessanterweise jedoch ist es jedocham besten und sind, wo alle Elemente im Array geschrieben werden. Sortiert ist O. N, was bedeutet, dass es nur durch das Array laufen muss. Was ist ziemlich cool, um zu testen, ob die Arrays bereits irgendwie, aber nicht so groß ist, das Array tatsächlich zu beschaffen. Also hier habe ich eine Website, die die 80. Ich empfehle Ihnen, es zu überprüfen. Es ist eine sehr, sehr interessante Ressource, wenn Sie Ihre verschiedenen Sortieralgorithmen lernen, dass es eine ganze Reihe von ihnen hat. Ich werde das während meiner gesamten Unterrichtsstunden verwenden. Also haben wir eine völlig unsortierte sehr 09328614 fünf auf sieben. Also im Wesentlichen, wie der Ball, so dass es funktioniert, wird mit benachbarten Partnern vergleichen. Im ersten Fall wird Null und neun sein. Es wird sehen, ob sie in ihrer richtigen Position sind. Wenn sie es nicht sind, wird es sie umdrehen. In diesem Fall wird nichts passieren. Aber wenn neun mit 39 und drei verglichen wird, werden wir umdrehen und die nächste werden Sie jetzt neun verglichen, weil es die größte in diesem Array wird weiter bis zum Ende der Liste sprudeln . Dann, wie wir durchgehen wird, werden H und H weiter nach oben sprudeln, immer nach rechts neben neun, dann sechs , etcetera, etcetera, etc. Ihre Arbeit. Werfen wir einen Blick darauf, wie das funktioniert. Okay, also neun kippt um und geht weiter, sprudelt ab, sprudelt den ganzen Weg bis zum Ende der Liste und zurück zum Anfang. Drei. Und um Agenten sechs zu wechseln. Was sagt. Sie können sehen, es sind nur diese Vergleiche zwischen diesen Paaren toe. Halten Sie sie in die richtige Position, und das ist normalerweise ineffizient, aber es tut es, und dann gehen wir dorthin. Wir haben unsere sortierte Liste oder Rate, also werde ich uns zurück zu dieser Visualisierung bringen. Nun lasst uns zuerst in einen Code springen, um zu sehen, was hinter den Vorhängen los ist. Ich habe diese Python-Datei oder eine Setup-Sortierung DuPuy anstelle meiner Beschaffung älterer Ordner auf genau das. Wir können diese gleiche Datei für alle verschiedenen Sourcing alten Räume verwenden, die wir tun. In dieser Lektion gehe ich auf diese Weise zum ältesten. Ich werde sagen, importieren Sie zufällig, äh, weiter. Und lassen Sie uns das Array erstellen, das wir Sourcing sind zufällige Elemente. Lassen Sie uns dies bereits mit zufälligen Riesen füllen Oh, sagen wir minus 52 100. Also werden wir zufällige ganze Zahlen zwischen minus 50 auf 100 vier auf einem Strahl von einer Länge von 20 erstellen . Okay, also nur, dass wir den Test testen können, die Algorithmen unten in den Dokumenten hier drüben . Ich werde sagen, Prinz, Prinz, vor zufälligen Gegenständen. Das geht also zu Prince The unsourced Array. Sie wollten die Beschaffung gewöhnlichen sie der Wahl nennen. In diesem Fall werden wir die formale Quelle aufrufen, die jetzt und plus zufällige Elemente zu ihm und Prinz danach implementieren wird, und das ist nur da, um sicherzustellen, dass das ältere als funktioniert. Lassen Sie uns also anfangen, eine Blase zu sortieren Tod, lokale Sortierungen zu implementieren , indem wir diese Elemente durchlaufen. Also das erste, was wir hier tun werden, ist tatsächlich durch die gesamte Rate von Null bis zur Länge von Artikeln laufen , die einen Safe für mich in Reichweite verkaufen. Danke. Oh, Gegenstände. Als nächstes werden wir diesen gesamten Bereich wieder durchlaufen, aber wir werden das Ende nicht erreichen, weil wir wissen, dass das größte Element in diesem Array bereits am Ende ist. Also für J Bereich aus machen Elemente minus eins minus I, was ist diese Variable? Dann werden wir sagen, wenn Artikel von J größer als Artikel O j plus eins ist. Im Wesentlichen ist das der Vergleich zwischen den beiden Elementen, um zu überprüfen, welches das größere der beiden ist , und dann werden wir sie wechseln. Jetzt gibt es zwei Möglichkeiten, sie zu wechseln. Traditionelle Programmiersprachen. Sie würden eine temporäre Variable erstellen und medizinische es temp Artikel ist gleich Artikel O. J. Und dann setzen wir Vitamine O. J Menschen zwei Elemente von J plus eins und dann sagt Artikel O J +12 temporizing. Das ist also sehr ausführlich. Und ich mag es nicht sehr auf Python hat eine ziemlich coole Art, das zu beschaffen, Sir. Werfen wir einen Blick darauf, was das ist. Nun, sagen Artikel von J Komma Artikel R J plus eins ist Menschen zwei Gegenstände von J plus eins meine Sünden. O Shea. Das wird genau das Gleiche tun. Und es ist nur viel eleganter bis zum Patent und Lesen. Lassen Sie uns also einen Blick darauf werfen, ob unser kleiner Bubble Sourcing Algorithmus hier nach Bedarf funktioniert . Ich bin bereits, ich habe mein Terminal hier geöffnet, und ich bin bereits innerhalb dieser Sourcing über Halter innerhalb dieses Ordners sortiert Punkt hoch. Also lassen Sie uns das ausführen und derzeit Python drei ausführen, aber Bindestrich zwei sollte perfekt funktionieren. Okay, Woche oben. Bevor wir also negative sechs negative 35 haben, die den ganzen Weg durch völlig zufällige ganze Zahlen zwischen minus 50 und 100 gehen, nachdem es aussieht, als wäre alles in Ordnung, von minus 50 bis zu 90. Wir wissen also, dass unser kleiner Algorithmus seine Arbeit geleistet hat. Werfen wir einen weiteren Blick auf diese Visualisierung, jetzt, wo wir wissen, was hier vor sich geht. Das ist also, ich sollte es einfach durchgehen. Ok. So vergleicht. Neun und drei und neun geht weiter bis zum Ende der Liste. Und dann sprudelt drei Blasen dieses h weiter bis zum Ende, und sechs Blasen den ganzen Weg bis rechts neben sieben. Und jetzt müssen wir nur den Test, den Sie wollen, in seine richtige Position bringen. Andi! Da haben wir es. Meine Damen und Herren, die Blasenquelle. Vielen Dank. Ich werde Sie in der nächsten Lektion sehen. 4. Sortierung: Guten Tag, meine Damen und Herren. Und willkommen zu dieser Lektion über die Einfüge-Sortierung in den grundlegenden Sourcing-Algorithmen und Pipe in Khost. Also lasst uns direkt in die Aufständischen von Werken springen, indem wir Elemente aus der unsortierten Liste und sie an der richtigen Stelle in eine neue Art von Liste einfügen. Die sortierte Liste ist leer. Der Anfang. Dies ist die Gesamtzahl der Elemente in der neuen und die alte Liste bleibt gleich. Wir können die nahtlose verwenden, um sortiert auf den unsortierten Abschnitten darzustellen. Also im Wesentlichen, was das bedeutet, ist, dass wir, wenn Rate entlang, vergleichen die verschiedenen Partner vollständig benachbarte Elemente, bis wir eines finden, das nicht an der richtigen Stelle ist und es nach unten in seine richtige -Position. Im Wesentlichen ist das Tun von Schaltern, wie wir auf der Blasen-Sortierung gesehen haben, wie eine Blase nach unten, wenn wir bestimmte Positionen Element finden . Lassen Sie uns also einen kurzen Blick auf die Effizienz werfen und dann eine Visualisierung machen. Thea Effizienz aus der Einfügequelle ist auch ausreichend. Brechen. Dies ist eine andere dieser akademischen Art ist, dass die schlechteste Leistung O. N Schweiß ist , sowohl bei Vergleichen als auch bei Swaps. Die durchschnittliche Fallleistung Owens Square als auch. Auf dem besten Fall führt ähnlich wie die Blase Sortierung ist OM, was bedeutet, dass alles in der richtigen Position ist, die nur einmal durch die Liste arbeiten muss . Werfen wir einen Blick darauf, wie das funktioniert. Zunächst einmal werden wir eins mit neun vergleichen. Wir werden sehen, dass sie darin richtige Ärzte sind. Dann wollte ich mit acht verglichen werden. Sie werden umschalten, dann neun wird sie zu voll jetzt für nichts geworden. Das ist die richtige Position. Also wird es an Ort und Stelle verschoben werden, wird mit acht verglichen und umgeschaltet und dann bewegen wir uns den ganzen Weg zurück zu neun und zwei und zwei ist nicht in seiner richtigen Position. Also werden wir die Liste runterziehen und wieder. Dort gehen wir, damit Sie sehen können, dass Sie den Trend von hier sehen können. Zero muss den ganzen Weg nach unten in der Liste bewegen. Sagt, dass es nicht in seiner richtigen Position ist, und ich werde das nur beschleunigen, jetzt, wo Sie den Kern dessen haben, was hier passiert . Wir haben sechs nach unten drei bewegen den ganzen Weg nach unten bis zum Anfang und dann Feuer wenn wir neben sechs auf sieben setzen, wird Zeug in seiner richtigen Position sein. Und dann haben wir die Quelle der Liste. Also lassen Sie uns einen Blick auf den Code werfen. Hier drüben haben wir auch die vom letzten Mal. Lassen Sie uns eine neue Funktion einfügen definieren. So nimmt nur in der Liste der Elemente. Sagen Sie nicht so, nur um sicherzustellen, dass wir dies nicht vergessen, Ich fügte Insertion Salsa hier hinzu. So werden Aufständische beide aufgerufen werden, wenn die Datei läuft. Zuerst brauchen wir Zehe ist das Rennen durch die gesamte Rate von eins bis zur Länge. Dieses nächste werden wir J Leute auf I setzen. Der Grund, warum wir J ableto Augen setzen, nur damit wir die Position haben , während wir aufgestiegen sind. Also, während J größer als Null ist, Sie einfach nicht das erste Element. Und Bison ist von Jay oder weniger, als Isis ausgeschaltet ist. Führerschein von J minus eins. Okay, dieser Vergleich von hier überprüft, ob, äh, wenn die benachbarten Elemente in ihrer richtigen Position sind und wenn sie in der falschen Position sind, wir werden sie umschalten, da wir nicht stoppt. Wir werden sagen, dass Elemente von J herauskommen, also j minus eins und Sie werden sehen, dass wir J minus eins anstelle von J plus eins verwenden , da wir nicht die Blasenquelle von der Ursache dafür sind, dass wir tatsächlich den Vergleich rückwärts machen , damit wir können weiter zu schalten diese in die richtige Ärzte. Tyson ist Off J minus einen Artikel aus, sagt J. Es dreht sich um, und dann ist der letzte und wahrscheinlich der wichtigste Teil das. Jay ist minus gleich eins. Was das also tun wird, ist, dass der Index nach unten verschoben wird, während diese Elemente nicht in der richtigen Position sind. Also überprüfen wir, um sicherzustellen, dass wir am Anfang nicht richtig sind, überprüfen wir, ob diese Dinge in Ordnung sind. Wenn sie nicht in Ordnung sind. Was wir tun, ist, dass wir sie umschalten und nach unten gehen, sie umschalten, nach oben gefahren sind. Okay, also schauen wir uns mal an, wie diese Zimmer Okay, also lasst uns, äh, sortieren. Nicht Und wieder diese Freunde der Pfeife in zwei und drei dort gehen wir bald haben wir eine ungesalzene Listen 97 85 3 42 21 Onda. Wir haben die Afterliste, die alle aussieht, als ob sie darauf sortiert wurde und sich in ihrer richtigen Position befindet. Nur für den Fall, dass du für die letzte Lektion nicht da warst, wir Jet. Wir generieren zufällig eine Liste von 2028 Zoll zwischen minus 50 auf 100, das ist das Array , das es sortiert ist. Werfen wir einen kurzen Blick auf die Sortierung dieser 18, um eine visuelle Darstellung dieser jetzt zu sehen, wo Sie uns besser verstehen. Ordnung, also neun Bewegungen im vollen Bewegungsstatus korrekte Position, um den ganzen Weg nach unten zu seiner richtigen Position zu bewegen, und Null bewegt sich den ganzen Weg durch. Das ist so wild auf den Tauben, die das J in drei Jahren bis zum Anfang ausstrahlen. Fünf. In diese richtige Position auf schließlich sieben in seine richtige Position. Nun, ich hoffe, dass dies Ihnen ein viel besseres Verständnis gibt, wie die Einfügungssortierung funktioniert und Ihnen auch ein besseres Verständnis dafür gibt, wie Sortieralgorithmen in der allgemeinen Arbeit Sie in der nächsten Lektion sehen müssen . Haben Sie eine große 5. Sorte zusammenführen: guten Tag, Damen und Herren, und willkommen zu diesem Video über die Merge-Sortierung in den grundlegenden Algorithmen in Python Video, Siri Let's Hop direkt in der Merge-Sorte. Es funktioniert, indem Sie die Liste in zwei Unterlisten unterteilen, sie mit merge sortieren, um Siple erneut zu wiederholen und sie dann wieder zusammenführen. Da die rekursive Umfrage gemacht wird, um jede Liste in eine Unterliste zu unterteilen, werden sie schließlich die Größe eines erreichen, was technisch eine sortierte Liste ist. Also werden wir eine schöne lange Liste von ganzen Zahlen haben. Wir werden das in zwei kleinere Listen zu kleineren Listen zu kleineren Listen unterteilen bis wir einzelne ganze Zahlen haben. Dann werden wir den rekursiven Aufruf verwenden, um sie an der richtigen Stelle zusammenzuführen , während sie gehen. Werfen wir einen Blick auf die Rechenkomplexität, so dass die Rechenkomplexität von der Emerge-Quelle in den schlechtesten besten im Durchschnitt Fällen alle o n log sind, und Sie sollten sich an unserer Video- und Rechenkomplexität erinnern, dass dies schrecklich, wie und quadratisch. Aber es ist nicht reich. Es ist fair. Es ist ein kurzer Blick darauf, wie die Fusion so funktioniert, wie wir in dem Bild hier haben, haben wir ein unsortiertes Array von 38 27 43 39 82 und 10. Wir teilen dieses Array in zwei, getrennt zu erhöhen oder zu Unterlisten, mit einem rekursiven cool, das 30 Alter 27 43 3 auf der einen Seite und 1982 und 10 auf der anderen Seite ist , und wir unterteilen jede dieser Listen als auch auf. Wir unterteilen uns weiter, bis wir einzelne Elemente durchlaufen haben. Jetzt wird die Anfrage von Cool sie wieder zusammenführen, während Vergleiche durchgeführt werden, um zu sehen, welches Element wohin geht. So werden 30 18 27 verschmolzen und miteinander verglichen. Also haben wir 27 38 43 3 sind miteinander verglichen, und es endet als Unterliste von drei und 43 das gleiche ist hier mit 1982 und schließlich 10 hier getan . Ehrlich einsam. Dann haben wir diese Unterlisten zusammenführen, um diese größeren Unterlisten zu erstellen Schließlich verschmelzen diese beiden Unterlisten miteinander und sie sind alle in der richtigen Reihenfolge sortiert 39 10 27 38 43 am Tag 82. Werfen wir einen kurzen Blick auf die Sortierung Done 80. Sortieren Sie, dass 80, wie ich meine vorherigen Videos erwähnt habe, ist eine fantastische Ressource für die Visualisierung von Sortieralgorithmen und eine sehr empfehlenswerte Sie überprüfen es. Sortierung Diät. Er ist vielleicht nicht der beste Weg, um die Fusionseele zu visualisieren, aber ich empfehle Ihnen, einen Blick zu werfen. Wir werden es später durchlaufen, gleich nachdem wir in den Code getreten sind. Also haben wir unsere öffentliche Sortierung und Einfüge-Sortierung vom letzten Mal. Lassen Sie uns hier eine neue Funktion davon definieren. Cold Merge Quelle nimmt es eine Reihe von Elementen auf Let's go. Wir werden sagen, wenn die Länge von Elementen größer als eins ist, dann wählen wir die Mitte, das ist die Länge von Elementen geteilt durch zwei. Sehen Sie etwas, das ein wenig über sie ist, und wir haben die meisten links. Die linke Zusammenfassung und Python hat eine schöne Möglichkeit, die linken Zusammenfassungen Elemente von Null bis zum Mittelpunkt zu definieren , und wir haben die richtige Zusammenfassung, die ITV ist. Nachrichten. Bis zum Ende ist eine schöne kleine Ausdrücke in Python und ich empfehle Ihnen, eine Einführung in den Python-Kurs zu machen , nur damit Sie mit all diesen phantasievollen Tricks sehr vertraut sind . Okay, also hier ist, wo der Rickerson innerhalb dieser Funktion passiert, wir werden tatsächlich die Quelle wieder mit der linken Zusammenfassung abkühlen, und wir werden merge aufrufen, sortieren mit der rechten Zusammenfassung . Im Wesentlichen wird das, was hier passiert, weitermachen und weitermachen, während die Länge der Lizenz ist, wenn die Länge der Gegenstände größer als eins ist. Okay, jetzt werden wir die linke auf der rechten Liste zusammenführen. Also sind wir weg, richtig? Es ist gleich Null ist Ihre. Das ist nur eine nette Möglichkeit, das zu definieren. Diese Indizes, die sagen würden, oder ich in Reichweite von Elementen lief durch den gesamten Strahl. Wir werden sagen, linker Wert, finden das definiert. Diese Variable ist gleich links am linken Index. Wenn der linke Index kleiner ist als die Länge ausgeschaltet ist, wenn das nicht der Fall ist, nein, lassen Sie uns dasselbe für Rechte tun. Wir sagen, der richtige Wert ist gleich dem Rechtearray am Index. Sind, wenn der richtige Index kleiner ist als die Länge aus, richtig, weil wir nicht wollen, dass Teoh immer wieder geht, werden wir sonst nein sagen. Würden Sie sagen, ob der linke Wert existiert und der rechte Wert existiert und der linke Wert kleiner als rechts ist . Dies ist also, wo der Vergleich gemacht wird oder wenn der richtige Wert keiner ist. Okay, der Grund, warum wir das tun, ist, weil es Chancen gibt, dass es eine einzelne Instanz auf beiden Seiten der Liste geben wird . Du wirst sagen, wenn das ist, dann sind es Gegenstände. Oh, ich, da wir hier immer noch durchtreten, ist gleich dem linken Wert. In Ordnung, also klebt es es in den besseren Ring. Wir werden sagen, links segnet die Menschen, nur von einem umgesetzt zu wollen, damit wir weiter durch die linke oder rechte treten können . Also, jetzt werden wir das Gleiche für die andere Seite tun. Wir werden sagen, wir werden sagen, wenn der linke Wert und der rechte Wert, stellen Sie sicher, dass sie existieren und linken Wert dieses Mal größer als oder gleich dem rechten Wert ist . Du wirst sagen, dass der oder der linke Wert hier nicht aufgestellt ist, dann machen wir den gleichen Film hier. Artikel alles, was ich ist Menschen zu hell Wert. Und dann erhöhen wir unseren Index beide, und das ist nur ein bisschen ein Scheck. Wir können bleiben. Ausnahme auslösen. Haubenklopfen verschmelzen, und es macht es beschreibender. Größen von Sub-Arrays stimmen nicht mit dem Haupt-Array überein. Großartig. Das ist also der Code. Werfen wir einen kurzen Blick durch es noch einmal, dass dies eine Bitte von cool ist. Wir werden sehen, wie wir das Array wieder in kleineren und kleineren Schritten durchlaufen . Wenn die Länge der Elemente größer als eins ist und die Mittelpunkte verfeinert, erstellen wir ein linkes und rechtes Array, und dann rufen wir die Zusammenführungssortierung auf der U-Bahn-Erhöhung auf. Darüber hinaus setzen wir einen Index für Links und Rechte um 00 Dann werden wir durchlaufen, denn ich bin regns, nicht wütend für die Länge weg, die diese Elemente haben wollten. Der linke Wert ist gleich dem Wert, der bei allen Index links ist. Wenn der Index kleiner als die Länge von links ist, stellen Sie sicher, dass er innen ist. Es ist in der Zusammenfassung sonst. Der linke Wert ist gleich none, die wir hier überprüfen werden. Dasselbe mit dem richtigen Wert. Es wird auf der rechten Zusammenfassung am Index sein unser Wenn unser kleiner ist als die Länge rechts trennen uns, ist unser Wert gleich nicht. Und wir werden den Scheck machen. Sagen wir, wenn der linke Wert auf dem rechten Wert auf dem linken Wert existiert, ist kleiner als der rechte Wert. Das ist dieser Vergleich. Oder wenn der richtige Wert keiner ist, dann rufen wir an. Dann werden wir Elemente von I gleich dem linken Wert ein Inkrement linken Wert setzen. Das Gleiche passiert hier, nur auf der rechten Seite. Und wenn eines davon fehlschlägt, werden wir eine Ausnahme auslösen, die besagt, dass sie nicht zusammenführen konnte. Die einzelnen Größen stimmen nicht mit der Hauptrate überein. Okay, lass uns hier drüben im Terminal laufen. Bindestriche sortieren Punkt und Ausführen. Okay, also haben wir die unsortierte Liste der Spitze, die ein zufälliges Array von Länge von 20 ist, die jede ganze Zahl zufällig zwischen minus 50 und 100 danach haben wir eine perfekt sortierte Liste. Fantastisch. Ich hoffe, dass das Ihnen wertvolle Einblicke in mörderische Lasten gegeben hat. Algorithmen im Allgemeinen, wie Rikers funktioniert. Wir sehen uns im nächsten Video. 6. Schnelle Sortierung: Guten Tag, meine Damen und Herren, und willkommen zu diesem Video über die schnelle Sortierung. Lass uns gleich drauf kommen. Die schnell verkaufte funktioniert, indem zuerst ein Schlüsselelement aus der Liste ausgewählt wird. Die Pivot-Elemente sind ziemlich grundlegend in der schnellen Sortierung auf, die Auswahl des Propheten Elements kann erhöhen oder verringern die Rechenkomplexität davon. Das Pivot-Element, das wir verwenden werden, wird das direkte Zentrum von der Liste oder dem Array sein , dann erstellt zwei Listen, dann erstellt zwei Listen, eine enthält Elemente weniger als die Öffentlichkeit und die andere, die Elemente enthalten, die mich eingestellt haben. Es greift dann die beiden Listen an und verbindet sie mit dem perfekten dazwischen, genau wie die Merge-Sortierung. Wenn die Listen in Listen der Größe 1 unterteilt sind, gelten sie als bereits sortiert. Auch, genau wie die Merge-Sortierung. Wir werden Rikers in ja verwenden, die Effizienz aus der schnellen Quelle im schlimmsten Fall ist O n quadriert, ähnlich wie die Blasensalze und nicht sehr effizient. Der beste Fall und die durchschnittliche Fallleistung R O N log und ähnlich der emerge sortieren, was nicht schlecht ist. Es ist auch nicht gut . Es ist fett. Nennen wir es fair. Lassen Sie uns eine Visualisierung der schnellen Sortierung machen. Nun, wie bei der Verschmelzungssorte, weil alles, was hinter dem Vorhang von Rikers sich geht, nicht viel Sinn ergeben kann. Also zuerst, was passiert, ist, dass wir einen Drehpunkt auswählen. Das ist die erste Belüftung durch sie, und wir werden uns in den Code eingraben, damit Sie besser verstehen, was von ihm passiert. Es findet These Eingabe von Marionette, und dann ist es Es wechselt diese beiden, aber es wechselt sie nicht wirklich. Was hinter den Kulissen passiert, ist, dass es die Sechs in die weniger als die Profit-Reihe bringt und die Neun in den größeren als den zentralen Ray bringt. Angenommen, das beweisen, dass es hier drüben fünf ist. Als Nächstes. wir durchgehen, schaltet es sieben und eins und wieder, wenn ich Schalter sage, bedeutet es, dass es einen in den weniger als einen Rechen setzt und sieben in den Ranger als Rick setzt. Dann haben wir voll in das weniger Jahrhundert und sechs setzen in das größere als Gelände auf. Schließlich haben wir 25 Schalter über jeden von ihnen, wählen Sie ihre eigenen Drehpunkt den ganzen Weg nach unten, und dann diejenigen, um zu wechseln und Wie Sie sehen können, beginnt es langsam die Schaffung eines sozialistischen, und schließlich sieben und jeder wird umgekippt. Da. Wir haben die sortierte Liste wieder. Dies ist nicht die beste Nutzung davon. Werfen wir einen Blick auf den Code, und ich denke, Sie werden ihn besser verstehen. Hier ist also die Sortierdatei DuPuy, die wir für die letzten paar Lektionen eingerichtet haben. Es hat ein zufälliges Element bereit, das ein Array von 20 Elementen lang ist, von denen jedes zufällig generiert wird. Zwischen minus 50 und 100 ist es, hier eine neue Funktion davon zu finden, genannt Wick Sorts. Schützt in der Liste der Elemente und die Aufnahme in der Liste der Elemente ist sehr wichtig, weil wir werden sie innerhalb der Funktion aufrufen, weil es regressiv ist. Ich habe hier auch schnell sortieren aufgerufen, um sicherzustellen, dass es die Funktion ist, die aufgerufen wird, wenn wir die Sortierung der hohen Datei ausführen. Alles klar, großartig. Also erste Dinge zuerst, wie bei der Merge-Sortierung würden sagen, ob die Länge der Elemente größer als eins ist, weil wie unterteilt, wir wollen Lager. Als nächstes wählen wir den privaten Index erneut aus. Dies könnte die Auswahl des Pivot-Index eine komplizierte Funktion sein, um zu versuchen den richtigen Platz für ihn zu finden. Aber in unserem Fall, und zu Demonstrationszwecken, werden wir es als die Länge der Rate geteilt durch zwei so tote Mitte haben. Als nächstes erstellen wir kleinere und größere Gegenstände erhöhen. Sie begannen als leer und werden sie die Natur bevölkern. Größere iTunes ist Menschen, um Rebsorten aufzuzeichnen. Fantastisch. Hier ist, wo die Magie beginnt zu geschehen. Es ist ein vier I. Ich wollte der Index sein, der unseren Platz halten wird und du, dass es der Wert von der Sache war , dass wir die Zähler-Sache durch Brillanz von Gegenständen aufzählen werden . Also wieder, ich halte den Index val, der Wert enthält. Du sagst, ich bin keine Leute, habe auch keinen Index, weil wir nicht wollen, dass die tatsächlichen Sehnsüchte wechseln. Dann, wenn Bogen weniger als Vereisungen aus innerhalb der nächsten, zwei machten den Vergleich, um zu sehen, ob es großartig ist, um sie oder weniger als acht Index auf, weil Wert weniger in der nächsten ist, nehmen Sie es und legen Sie es in kleinere Elemente und und dann, wenn es nicht weniger als aber ist in der Tat größer als oder auf nicht gleich, weil wir tun, dass überprüfen dort und sicher sonst. Größere Iceman's macht einen Pendelwert fantastisch, also wäre dies kein rekursives Array ohne einen rekursiven Cool. Es würde einfach einmal durchlaufen, und Sie haben ein kleines bisschen mehr von uns. Eigentlich wäre es nur ein einzelnes Element, das in den Vorort Razzien Nazi-Sorten stecken bleibt, kleinere Gegenstände. Also im Wesentlichen, was da passiert ist, ist, dass wir schnell jede einzelne Antwort den ganzen Weg nach unten beschaffen werden . So jeder trennt wählt seinen eigenen begehrten Index. Es schafft eine kleine Lizenz und größere Vereisungen Strahlen auf und jeder von ihnen bekommt dann eine Art von dieser Art Frankreich. Es sortiert groß, entstehen Frau Well, und schließlich, was wir tun werden, ist, dass wir Dinge sagen, die kleineren Gegenständen entsprechen, plus der davon investiert plus größere Gegenstände. Dann näht das alles am Ende zusammen. Also haben wir kleinere Elemente, und dann in der Mitte haben wir Indexelemente, und dann haben wir die größeren Elemente. Also schauen wir es uns einfach von oben an. Wir werden sicherstellen, dass die Länge von jedem von ihnen Nein ist. Eins. Wir werden einen Pivot-Index auswählen, kleinere und größere Ice Marie's deklarieren und dann werden wir laufen. Wir werden durch die Elemente auf aufzählen. Wir werden sie in kleinere oder größere Raise stecken, je nachdem, wo sie sein sollten. Und schließlich werden wir uns schnell zusammenfassen, jede dieser Zusammenfassungen sortieren. Werfen wir einen kurzen Blick, sehen, ob das funktioniert. Sie haben meine Sortierung P. WiFi an. Ich werde es laufen, dachte ich, oben sortieren. Und wie Sie sehen können, haben wir ein unsortiertes Wir haben nicht am meisten unsortiert. 28 26 93 minus zwei auf, nachdem wir eine völlig Art Rate von minus 50 bis 98. Fantastisch. Wir wussten, dass unsere Reihe der Pille funktioniert. Werfen wir noch einmal einen zweiten Blick auf die Visualisierung. Die Visualisierung ist nicht alles so aussagekräftig wegen all dem Rickerson, der passiert, aber es ist interessant zu beobachten und zu gehen. Also gehen wir davon aus, dass das Primitive hier fünf ist, und diese werden in ihre größeren oder kleineren diese größeren oder kleineren Zusammenfassungen umgestellt, auch die schnelle Art von manchmal genannt die Petition Austausch verkauft, was ich glaube, ist ein viel mehr apt Namen als tatsächlich Partitionierung und dann Sortieren jeder dieser verschiedenen Partitionen. Oh, du verstehst die schnelle Art von winzigen, aber besser auf alten Rhythmen im Kampf im Allgemeinen. Vielen Dank, dass Sie sich mir angeschlossen haben. Haben Sie ein fantastisches Date.