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?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…
Entdecke über 200 Millionen kostenlose Materialien 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.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.