Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Insertion Sort Algorithmus [Einfach erklärt, Deutsch]
Das Wichtigste aus dem Video
Transkriptautomatisch erstellt · 48 Zeilen
- 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.
- Fangen wir an. Insertion Sort funktioniert im Grunde genommen so, wie man Spielkarten in die Hand einsortiert. Hier ein Beispiel:
- 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.
- 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,
- 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."
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Und jetzt kommen wir, wie versprochen – mit einfachsten mathematischen Mitteln – zur Zeitkomplexität von Insertion Sort:
- 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 –
- ... 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.
- Im Durschnitt also ein Mal. Im dritten Schritt verschieben wir kein Mal, ein Mal, zwei Mal oder drei Mal.
- Im Durchschnitt also eineinhalb Mal. Im vierten Schritt kommen wir auf zwei Mal und im fünften auf 2,5 Mal.
- In der Summe kommen wir auf durchschnittlich 7,5 Verschiebungen. Das kann man auch wie folgt ausrechnen: 6 Elemente ... mal 5 Schritte ...
- … 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
- 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.
- 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.
- 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.
- Und das bedeutet: Die Zeitkomplexität von Insertion Sort ist im average case – auf deutsch: im durchschnittlichen Fall – O von n Quadrat.
- 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.
- 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.
- 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.
- 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.
- 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,
- 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 …
- … 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.
- 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
- Oder: n x (n-1) x ½ Der Term enthält wieder: n mal n. Und damit wie vorhin auch: n Quadrat.
- 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.
- 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.
- Die Anzahl dieser Operationen entspricht dabei der Anzahl der Elemente, n … ... minus 1, weil wir ja beim zweiten Element mit dem Vergleichen beginnen.
- Wir haben also kein n², sondern nur ein n. Und das bedeutet: Die Zeitkomplexität ist im best case: O von n.
- “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.
- Mein Laptop misst hierfür 0,04 Millisekunden. Bei 1.000.000 Elementen sind es 0,32 Millisekunden.
- Bei 10 Millionen Elementen: 3,05 Millisekunden. Bei 100 Millionen: 30,4 Millisekunden.
- 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:
- Für eine nicht sortierte Liste – also bei quadratischem Aufwand – hätte das Sortieren von 1 Milliarde Elementen über 3 Jahre gedauert.
- Hier nochmal zusammengefasst: Die Zeitkomplexität von Insertion Sort beträgt im average und im worst case: O von n Quadrat.
- 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.
- 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.
- 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.
- 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.
- 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!
- Bis bald und Happy Coding!