StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
Stelle Dir vor, Du erhältst bei einem Kartenspiel 10 Karten auf die Hand. Wie würdest Du sie sortieren?
Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenStelle Dir vor, Du erhältst bei einem Kartenspiel 10 Karten auf die Hand. Wie würdest Du sie sortieren?
Die meisten Menschen würden einfach links beginnen, Karte für Karte durchgehen und diese weiter vorn einsortieren, wenn nötig. Und damit bist Du schon mittendrin im Thema, denn Insertion Sort macht im Grunde nichts anderes.
Was genau bedeutet denn nun Insertion Sort? Insertion Sort ist ein Algorithmus, der eine Datenmenge sortiert, indem er sie von vorn bis hinten durchgeht, die Elemente vergleicht und bei Bedarf ein Element entnimmt und weiter vorn wieder einsetzt.
Insertion Sort besteht aus den zwei englischen Begriffen insertion ("Einfügung") und sort ("sortieren") und wird deshalb auf Deutsch manchmal auch als "Sortieren durch Einfügen" bezeichnet.
Wie funktioniert Insertion Sort? Grundsätzlich geht der Algorithmus die gesamte Menge an Elementen durch. Dabei gilt die Menge vor dem aktuellen Laufindex als sortiert, und die Menge nach dem Index als unsortiert.
Das aktuelle Element wird dabei mit den vorhergehenden Elementen verglichen, bis die passende Stelle gefunden ist. An dieser Stelle wird das Element dann eingefügt. Es kann aber auch sein, dass das Element bereits an seiner richtigen Position war.
In beiden Fällen geht es mit dem nächsten Element weiter, solange noch als unsortiert geltende Elemente vorhanden sind.
Am besten lässt sich die Funktionsweise von Insertion Sort an einem Beispiel demonstrieren. Gegeben sei eine Menge von Zahlen [7, 3, 9, 2, 1, 4], die aufsteigend sortiert werden soll.
Das erste Element in der Menge kann grundsätzlich übersprungen werden, da es kein vorheriges Element gibt, mit dem es verglichen werden könnte.
Iteration | Erklärung | Ergebnis |
1 | Das zweite Element ist kleiner als das erste und wird davor eingefügt. | [3, 7, 9, 2, 1, 4] |
2 | Die 9 ist größer als 7 und muss daher nicht bewegt werden. | [3, 7, 9, 2, 1, 4] |
3 | Die 2 ist kleiner als die 9 vor ihr. Sie wird aber so lange mit den vorherigen Elementen verglichen, bis die passende Stelle gefunden ist. In diesem Fall ist die 2 kleiner als alle Elemente vor ihr, und kommt daher an den Anfang der Zahlenreihe. | [2, 3, 7, 9, 1, 4] |
4 | Als Nächstes wird die 1 untersucht. Sie ist ebenfalls kleiner als alle Elemente vor ihr und kommt an den Anfang der Menge. | [1, 2, 3, 7, 9, 4] |
5 | Das letzte Element im unsortierten Bereich ist die 4. Sie ist kleiner als 7, aber größer als die 3, und wird daher gleich nach der 3 eingefügt. Somit ist die Menge nun aufsteigend sortiert! | [1, 2, 3, 4, 7, 9] |
Wie Du siehst, durchläuft der Algorithmus also die Menge von vorn bis hinten und schaut in diesem Fall, ob das aktuelle Element kleiner ist als die vorherigen Elemente. Dann schiebt er dieses Element weiter nach vorne, wenn nötig.
Durch das folgende Struktogramm wird die Funktionsweise und der Ablauf von Insertion Sort noch einmal besser verdeutlicht. Es liefert außerdem die Grundlage für eine mögliche Implementierung.
Abb. 1 - Insertion Sort Struktogramm
Was den zusätzlich benötigten Speicherplatz angeht, ist der Algorithmus sehr effizient.
Das Sortieren der Elemente geschieht in-place. Außer den benötigten Hilfsvariablen wird nichts zwischengespeichert, sodass der benötigte Platz unabhängig von der zu sortierenden Mengengröße ist. Die Platzkomplexität ist also konstant und beträgt hier O(1).
Doch wie sieht es mit der Zeitkomplexität aus?
Du siehst bereits an dem oberen Beispiel, dass der Algorithmus mit zwei ineinander verschachtelten Schleifen arbeitet. Die erste Schleife durchläuft die Menge von vorn bis hinten. Die zweite Schleife vergleicht das aktuelle Element mit allen vorherigen Elementen, bis der passende Platz dafür gefunden ist.
Du siehst an dem Beispiel auch, dass die zweite Schleife bis ganz an den Anfang der Menge zurücklaufen muss, wenn das zu sortierende Element das bisher kleinste ist. Das kann bei großen und unsortierten Mengen schnell ineffizient werden.
Die beiden Schleifen haben jeweils eine Zeitkomplexität von O(n), weshalb sich für den Algorithmus eine Gesamtkomplexität von O(n²) ergibt.
Falls Du Nachholbedarf zum Thema Zeitkomplexität hast, findest Du mehr dazu in der Erklärung zur O-Notation.
Zum Verständnis von Insertion Sort und dem Vergleich mit anderen Sortieralgorithmen werden im Folgenden noch weitere Begrifflichkeiten erklärt.
Insertion Sort verändert die Anordnung der Elemente nur, wenn sich das zu sortierende Element tatsächlich unterscheidet. Wenn es gleich groß ist wie ein vorstehendes Element, wird es nicht verschoben.
Damit bleibt die Anordnung gleich großer Elemente immer erhalten. Insertion Sort ist also ein stabiler Sortieralgorithmus.
Insertion Sort gehört zu den vergleichsbasierten Sortieralgorithmen. Der Algorithmus vergleicht also immer zwei Elemente miteinander, um über die Anordnung in der Datenmenge zu entscheiden.
Normalerweise implementiert man Insertion Sort iterativ, aber auch eine rekursive Implementierung ist möglich. Diese eignet sich jedoch mehr für Übungszwecke, denn es ist zu bedenken, dass bei der rekursiven Variante die Platzkomplexität des Algorithmus O(n) beträgt statt O(1).
O(1) beschreibt einen konstanten Aufwand eines Algorithmus. Der Aufwand ist dabei also unabhängig von der Eingabegröße. O(n) ist hingegen ein linearer Aufwand, also wächst der Aufwand dabei linear mit der Eingabegröße an.
Der Insertion Sort Algorithmus ist nicht vollständig parallelisierbar.
Es gibt allerdings den Sortieralgorithmus Shellsort, der eine Erweiterung von Insertion Sort darstellt. Dieser ist zwar parallelisierbar, allerdings hat er nicht mehr die stabile Eigenschaft von Insertion Sort.
Mehr zum Shell Sort Algorithmus findest Du in der entsprechenden Erklärung dazu.
In der folgenden Tabelle findest Du die wichtigsten Eigenschaften von Insertion Sort übersichtlich zusammengefasst.
Best Case | Average Case | Worst Case | Platzkomplexität | Stabiles Verfahren | vergleichsbasiert | In-place | Parallelisierbarkeit | iterativ/rekursiv |
O(n) | O(n²) | O(n²) | O(1) | Ja | Ja | Ja | Nicht parallelisierbar | Beides möglich |
Wie jedes andere Sortierverfahren hat auch Insertion Sort seine Vor- und Nachteile.
Vorteile | Nachteile |
Einfache Implementierung | Ineffizient bei großen Datenmengen |
Verständlichkeit | Nicht parallelisierbar |
Das Problem des Insertion Sort Sortieralgorithmus zeigt sich schnell, wenn man mit großen und nicht vorsortierten Datenmengen arbeitet. Der Algorithmus arbeitet ineffizient, weil er eine große Anzahl an Vergleichen benötigt und weit über die Datenmenge iterieren muss. Das zeigt sich an der kostenintensiven, quadratischen Laufzeit im Worst-Case-Szenario.
Zum Abschluss findest Du hier noch eine Implementierung von Insertion Sort in Pseudocode.
function InsertionSort (List items) // Iteriere von vorn bis hinten durch die Liste. for i = 0 to items.length - 2 do: nextIndex = i + 1 // Dieses Element wird mit den vorigen in der Liste verglichen. nextElem = items[nextIndex] // Schiebe alle vorigen Elemente so lange nach vorne, bis der richtige Platz für nextElem gefunden ist. while nextIndex > 0 AND nextElem < items[nextIndex - 1] do: items[nextIndex] = items[nextIndex - 1] nextIndex -= 1 // Füge nextElem an der passenden Stelle ein. items[nextIndex] = nextElem
Wie Du siehst, ist die Implementierung von Insertion Sort nicht besonders aufwendig und relativ leicht verständlich.
Der Insertion Sort Algorithmus iteriert von vorn bis hinten über die Datenmenge, vergleicht das aktuelle Element mit vorherigen Elementen und setzt es an der passenden Stelle ein.
Man benutzt Insertion Sort vor allem bei kleineren oder vorsortierten Datenmengen, da der Algorithmus bei großen Datenmengen schnell ineffizient wird.
Insertion Sort ist stabil, weil nur Elemente umsortiert werden, die nicht dem vorherigen Element in der Folge gleichen. Die Reihenfolge gleicher Elemente bleibt somit immer erhalten.
Im ersten Schritt wird das nächste unsortierte Element in der Datenfolge gesucht. Im zweiten Schritt wird die richtige Position für dieses Element ermittelt und es wird dort eingefügt.
Karteikarten in Insertion Sort15
Lerne jetztWelche Laufzeitkomplexität hat Insertion Sort im Worst Case Szenario?
O(n²)
Welche Platzkomplexität hat Insertion Sort bei iterativer Implementierung?
O(1), also einen unabhängig von der Eingabegröße konstanten Aufwand
Warum ist Insertion Sort ein stabiler Sortieralgorithmus?
Der Algorithmus verändert nicht die Anordnung gleich großer Elemente.
Wahr oder falsch
Insertion Sort arbeitet nicht vergleichsbasiert.
Falsch
Wahr oder falsch
Insertion Sort kann vollständig parallelisiert implementiert werden.
Falsch
Warum ist eine rekursive Implementierung von Insertion Sort nicht empfehlenswert?
Weil dann die Platzkomplexität statt einem konstanten Aufwand einen linearen Aufwand benötigt.
Du hast bereits ein Konto? Anmelden
Open in AppDie erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.
Melde dich an für Notizen & Bearbeitung. 100% for free.
Speichere Erklärungen in deinem persönlichen Bereich und greife jederzeit und überall auf sie zu!
Mit E-Mail registrieren Mit Apple registrierenDurch deine Registrierung stimmst du den AGBs und der Datenschutzerklärung von StudySmarter zu.
Du hast schon einen Account? Anmelden