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
Tipp auf eine Zeit – das Video springt genau dorthin.
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!
Zum Nachlesen
GnomesortGnomesort ist ein sehr einfacher und stabiler Sortieralgorithmus. Animation von Insertionsort bzw. von Gnomesort ohne Visualisierung der …
BubblesortBubblesort (auch Sortieren durch Aufsteigen oder Austauschsortieren) ist ein Algorithmus, der vergleichsbasiert eine Liste von Elementen sortiert.
ShakersortDer Begriff Shakersort bezeichnet einen stabilen Sortieralgorithmus, der eine Menge von linear angeordneten Elementen (z. B. Zahlen) der Größe nach sortiert …
Merge InsertionMerge Insertion (auch bekannt als Ford-Johnson-Algorithmus) ist in der Informatik ein rekursives, vergleichsorientiertes Sortierverfahren, das mit weniger …