Insertion Sort Algorithmus [Einfach erklärt, Deutsch]
HappyCoders
https://www.youtube.com/watch?v=0hiSJFeUhj4

Transkript (automatisch erstellt)

0:00 In diesem Video zeige ich dir, wie "Insertion Sort" funktioniert und wie man seine Zeitkomplexität bestimmt. Und zwar ohne komplizierte mathematische Beweise … … dafür mit einem Beispiel, mit Animationen und V isualisierungen.
0:14 Fangen wir an. Insertion Sort funktioniert im Grunde genommen so, wie man Spielkarten in die Hand einsortiert. Hier ein Beispiel:
0:23 Die erste Karte nimmst du einfach auf die Hand. Die zweite Karte sortierst du dann links oder rechts davon ein. Hier die 2 also nach links.
0:32 Die dritte Karte sortierst du links, in der Mitte oder rechts ein. In diesem Fall kommt die 4 in die Mitte. Genauso machst du mit den restlichen Karten weiter: Die 10 kommt nach rechts,
0:44 die 3 zwischen die erste und zweite Karte, und die 7 fügst du zwischen der 6 und der 10 ein. Hier nochmal der letzte Satz zum Mitschreiben: "Die 7 fügst du zwischen der 6 und der 10 ein."
0:56 Wir sortieren also durch “Einfügen” … englisch “Insertion” … daher der Name “Insertion Sort”. Ein Computer hat natürlich keine Hände und muss hier etwas anders vorgehen.
1:07 Hier gibt es auch keinen Kartenstapel, sondern ein Array, dass die Elemente enthält, die sortiert werden sollen. In diesem Fall die unsortierten Zahlen aus dem Kartenbeispiel.
1:17 Wir teilen das Array gedanklich auf, in einen linken Teil, der schon sortiert ist – die erste Karte für sich gilt als sortiert – und den rechten, unsortierten Teil. Jetzt schauen wir auf die erste Zahl des unsortierten Teils – dies entspricht im Kartenbeispiel dem Aufnehmen einer Karte vom Stapel.
1:35 Hier haben wir die 2, und die sortieren wir links neben die 6, in dem wir diese nach rechts schieben und die 2 links davon einfügen. Die Grenze zwischen sortiertem und unsortiertem Bereich verschiebt sich jetzt um eine Position nach rechts.
1:48 Wir schauen auf die nächste Zahl, die 4. Diese gehört zwischen die 6 und die 2. Also schieben wir die 6 nach rechts und fügen die 4 hier ein.
1:58 Die 10 ist schon an der richtigen Stelle; in diesem Schritt müssen wir also nichts verschieben. Die 3 gehört zwischen die 2 und die 4.
2:06 Wir verschieben daher die 10, die 6 und die 4 jeweils um eine Position nach rechts und setzen die 3 auf das freigewordene Feld. Und zuletzt tauschen wir noch die 7 mit der 10. Und damit sind alle Zahlen sortiert.
2:23 Und jetzt kommen wir, wie versprochen – mit einfachsten mathematischen Mitteln – zur Zeitkomplexität von Insertion Sort:
2:30 Die Anzahl der zu sortierenden Elemente bezeichnen wir mit n; in unserem Fall ist n = 6. Im ersten Schritt müssen wir entweder gar nicht verschieben – wenn die zweite Karte größer ist als die erste –
2:43 ... oder ein Mal, wenn sie kleiner ist. Im Durchschnitt also ein halbes Mal. Im zweiten Schritt müssen wir kein Mal, ein Mal, oder zwei Mal verschieben.
2:52 Im Durschnitt also ein Mal. Im dritten Schritt verschieben wir kein Mal, ein Mal, zwei Mal oder drei Mal.
2:59 Im Durchschnitt also eineinhalb Mal. Im vierten Schritt kommen wir auf zwei Mal und im fünften auf 2,5 Mal.
3:07 In der Summe kommen wir auf durchschnittlich 7,5 Verschiebungen. Das kann man auch wie folgt ausrechnen: 6 Elemente ... mal 5 Schritte ...
3:18 … geteilt durch zwei, da im Durchschnitt die Hälfte der Karten schon sortiert ist ... … und nochmal geteilt durch 2, da im Durchschnitt das einzusortierende Element
3:27 bis zur Mitte der sortierten Elemente geschoben werden muss. 6 mal 5 ist 30 … geteilt durch 2 ist 15 ... nochmal geteilt durch zwei ist 7,5.
3:40 Ersetzen wir 6 durch n, dann ergibt das: n mal n-1 (das muss in Klammern) ... mal ½ … mal ½. Und "½ mal ½" können wir zu einem Viertel zusammenfassen.
3:54 Das könnten wir jetzt noch ausmultiplizieren ... müssen wir aber nicht. Wir wollen es uns ja so einfach wie möglich machen. Uns reicht an dieser Stelle die Tatsache, dass n mit n multipliziert wird – im ausmultiplizierten Term also irgendwo n Quadrat vorkommt.
4:10 Und das bedeutet: Die Zeitkomplexität von Insertion Sort ist im average case – auf deutsch: im durchschnittlichen Fall – O von n Quadrat.
4:20 O von n Quadrat … oder auch “quadratischer Aufwand” bedeutet: Die benötigte Zeit wächst im Quadrat mit der Anzahl der zu sortierenden Elemente. Ein Beispiel: Insertion Sort braucht für 100.000 Elemente auf aktueller Hardware etwa 1 Sekunde.
4:38 Für 100 Millionen Elemente (also tausendmal so viele) würde es nicht etwa 1.000 Sekunden benötigen, sondern eine Sekunde mal Tausend zum Quadrat, also 1.000.000 Sekunden. Das sind 278 Stunden.
4:54 Bei einer Milliarde Elemente wären es drei Jahre und zwei Monate. Quicksort schafft 100 Millionen Elemente in acht Sekunden und eine Milliarde Elemente in eineinhalb Minuten.
5:08 Aber dazu mehr in einem anderen Video. Wo es einen average case gibt, gibt es auch einen best und einen worst case … also einen besten und einen schlechtesten Fall.
5:19 Im schlechtesten Fall sind die Elemente zu Beginn komplett absteigend geordnet. Das bedeutet, dass in jedem Schritt das einzusortierende Element ganz nach links gehört,
5:30 also alle bereits sortieren Elemente nach rechts geschoben werden müssen. Im ersten Schritt müssen wir also ein Mal verschieben, im zweiten zwei Mal … und so weiter …
5:41 … bis wir am Ende 15 Elemente verschoben haben. Hier nochmal zum Vergleich die Zahlen vom average case: Hier waren es jeweils halb so viele Operationen.
5:52 Berechnen können wir diese Zahl so wie im average case, nur dass wir das letzte Teilen durch zwei weglassen, also: 6 mal 5 mal ½ … ist 15
6:04 Oder: n x (n-1) x ½ Der Term enthält wieder: n mal n. Und damit wie vorhin auch: n Quadrat.
6:15 Die Zeitkomplexität ist also auch im worst case: O(n²). Der Best Case wird allerdings interessant! Wenn die Elemente nämlich bereits aufsteigend sortiert sind ... dann muss kein einziges Element verschoben werden.
6:30 Das heißt natürlich nicht, dass der Algorithmus jetzt gar keine Zeit benötigt. Er muss sich ja immer noch jedes Element anschauen und mit seinem linken Nachbarn vergleichen.
6:39 Die Anzahl dieser Operationen entspricht dabei der Anzahl der Elemente, n … ... minus 1, weil wir ja beim zweiten Element mit dem Vergleichen beginnen.
6:49 Wir haben also kein n², sondern nur ein n. Und das bedeutet: Die Zeitkomplexität ist im best case: O von n.
6:57 “O von n” oder auch “linearer Aufwand” bedeutet: Die benötigte Zeit wächst linear mit der Anzahl der zu sortierenden Elemente. Mit 100.000 vorsortierten Elementen, wie im letzten Beispiel, brauchen wir Insertion Sort nicht zu kommen.
7:11 Mein Laptop misst hierfür 0,04 Millisekunden. Bei 1.000.000 Elementen sind es 0,32 Millisekunden.
7:19 Bei 10 Millionen Elementen: 3,05 Millisekunden. Bei 100 Millionen: 30,4 Millisekunden.
7:27 Und bei einer Milliarde Elemente: 284 Millisekunden, also gerade mal etwas mehr als eine Viertelsekunde. Der lineare Anstieg ist sehr gut zu erkennen. Zur Erinnerung:
7:39 Für eine nicht sortierte Liste – also bei quadratischem Aufwand – hätte das Sortieren von 1 Milliarde Elementen über 3 Jahre gedauert.
7:48 Hier nochmal zusammengefasst: Die Zeitkomplexität von Insertion Sort beträgt im average und im worst case: O von n Quadrat.
7:55 Und im best case, wenn die Zahlen komplett sortiert sind: O von n. Ich hoffe dir hat dieses Video geholfen Insertion Sort und dessen Zeitkomplexität zu verstehen.
8:05 Du kannst das ganze auch nochmal nachlesen auf happycoders.eu – einen Link findest du in der Video-Beschreibung. Auf der Webseite findest du auch den Quellcode von Insertion Sort und anderen Sortieralgorithmen.
8:16 Wenn dir das Video gefallen hat, dann abonniere gleich meinen YouTube-Kanal. So verpasst du nicht mein nächstes Sortieralgorithmus-Video. Klicke dazu einfach auf den “Abonnieren”-Button unter diesem Video.
8:26 Und wenn du dich für weitere How-Tos und Tutorials zu Java, Algorithmen und Datenstrukturen interessierst, gehe auf HappyCoders.eu und trage dich in meinen E-Mail-Verteiler ein.
8:36 Und jetzt eine Frage an dich: Welchen Sortieralgorithmus soll ich als nächstes erklären? Selection Sort? Quicksort? Merge Sort? Oder einen anderen? Schreib mir einen Kommentar!
8:48 Bis bald und Happy Coding!