Die Einfügesortierung ist im Grunde ein Sortieralgorithmus. Er kann bei jeder einzelnen Iteration verschiedene unsortierte Elemente an den für sie am besten geeigneten Stellen platzieren. Man kann sagen, dass dieser Algorithmus ähnlich funktioniert wie das Sortieren von Karten auf der Hand. Wenn Sie Erfahrung mit Kartenspielen haben, werden Sie wissen, dass Kartenspieler beim Sortieren davon ausgehen, dass die ersten Karten bereits sortiert sind, und dann die unsortierten Karten auswählen.

Ist die unsortierte Karte größer als die Karte in der Hand des Spielers, muss er sie auf die rechte Seite legen. Andernfalls müssen sie die Karte auf der linken Seite ablegen. In ähnlicher Weise müssen Sie die restlichen unsortierten Karten an ihren jeweiligen Platz legen und aufbewahren. Die Vorgehensweise bei der Einfügesortierung ist dieser Vorgehensweise sehr ähnlich.

Die Grundlagen der Einfügungssortierung

Im Folgenden wird die Funktionsweise der Einfügesortierung in drei Schritten beschrieben:

• Im ersten Schritt werden die in Frage kommenden Elemente mit den benachbarten Elementen verglichen
• Wenn jeder Vergleich ergibt, dass das betreffende Element an einer bestimmten Position verwendet werden kann, wird dafür Platz geschaffen. Dies geschieht, indem die Position der anderen Elemente nach rechts verschoben wird.
• Dieser Vorgang wird so lange fortgesetzt, bis jedes Element im Array seine richtige Position gefunden hat.

Merkmale der Einfügungssortierung

Dieser Sortieralgorithmus hat eine Vielzahl von Eigenschaften, aber es gibt drei wichtige, mit denen jeder vertraut sein sollte.

• Erstens ist der Insertion-Sort-Algorithmus unglaublich einfach. Manche würden sogar sagen, dass er aufgrund seiner unkomplizierten Implementierung der einfachste Algorithmus überhaupt ist.
• Wenn Sie ein Programmierer sind, der regelmäßig mit kleinen Datenwerten zu tun hat, wird die Verwendung dieses Algorithmus sehr nützlich sein
• Der Insertion-Sort-Algorithmus ist recht anpassungsfähig, was ihn ideal für teilweise sortierte Datensätze macht.

Häufig gestellte Fragen zu Insertion Sort

Hier finden Sie eine Liste mit kurzen Antworten auf häufig gestellte Fragen zu den Insertion-Sortieralgorithmen.

Was sind die Grenzfälle des Insertion Sort Algorithmus?

Die Einfügesortierung erfordert viel Zeit, wenn die Elemente in umgekehrter Reihenfolge sortiert werden sollen. Wenn die Elemente jedoch bereits sortiert sind, wird nicht viel Zeit benötigt.

Sind Algorithmen für die Einfügesortierung stabil?

Einfügungssortieralgorithmen sind unglaublich stabil, vor allem wenn man sie mit anderen Algorithmen vergleicht.

Wann ist der beste Zeitpunkt für die Verwendung des Insertion-Sort-Algorithmus?

Wie bereits erwähnt, wird die Einfügesortierung häufig verwendet, wenn die Anzahl der Elemente gering ist. Sie kann aber auch sehr nützlich sein, wenn ein Eingabefeld nicht allzu viel sortiert werden muss und nur wenige fehlplatzierte Elemente enthält.

Welcher Ansatz wird bei der Einfügesortierung verfolgt?

Der Ansatz, den der Insertion-Sort-Algorithmus verfolgt, ist inkrementell, weshalb er bei Programmierern, die Arrays sortieren, unglaublich beliebt ist.

Binäre Einfügesortierung erklärt

Programmierer können die binäre Suche nutzen, um die Anzahl der Vergleiche bei der regulären Einfügesortierung zu reduzieren. Die binäre Einfügesortierung nutzt die Suche, um bei jeder einzelnen Iteration die ideale Stelle für das Einfügen des gewählten Elements zu finden. Bei der regulären Einfügung benötigt die Sortierung im schlimmsten Fall O(i) (bei der i-ten Iteration).
Mit Hilfe der Binärforschung können wir diesen Wert reduzieren: O(logi). Trotzdem hat der Algorithmus im schlimmsten Fall immer noch eine Laufzeit von etwa O(n^2). Dies ist auf die Anzahl der pro Einfügung erforderlichen Vertauschungen zurückzuführen.

Schritte zur Implementierung von Insertion Sort in Linked Lists

Die folgenden Schritte zeigen, wie man den Einfügesortieralgorithmus in einer verknüpften Liste verwenden kann.

• Beginnen Sie mit der Entwicklung einer sortierten Liste und stellen Sie sicher, dass diese leer ist.
• Durchlaufen Sie die von Ihnen erstellte Liste und führen Sie diesen Schritt für jeden Knoten aus
• Geben Sie den aktuellen Knoten in Form eines Ergebnisses oder einer sortierten Liste ein.
• Ändern Sie schließlich den Kopf der verknüpften Liste und machen Sie ihn zum Kopf der sortierten Liste, auch Ergebnisliste genannt.

Die wichtigsten Anwendungen von Insertion Sort

Hier sind zwei der häufigsten Szenarien, in denen Programmierer die Einfügesortierung verwenden.

– Erstens wird sie immer dann verwendet, wenn es ein Array mit wenigen Elementen gibt.
– Die Einfügesortierung kann auch nützlich sein, wenn nur eine kleine Anzahl von Elementen zu sortieren ist.

Zeitkomplexe bei der Einfügungssortierung

Hier ist ein Blick auf die Zeitkomplexität, die bei der Einfügesortierung auftreten kann.

Schlimmster Fall: Komplexität O (n2) – Worst Case Complexity O (n2)
Stellen Sie sich vor, dass ein Array in aufsteigender Reihenfolge vorhanden ist, das Sie in absteigender Reihenfolge sortieren wollen. Ein solcher Fall führt zu einer Worst-Case-Komplexität. In einer solchen Situation müssen Sie jedes Element mit anderen Elementen vergleichen, um sicherzustellen, dass es (n-1) Vergleiche für jedes n-te Element gibt.

Die Gesamtanzahl der Vergleiche beträgt n*(n-1) ~ n2

Durchschnittliche Fallkomplexität O(n) – Average Case Complexity O(n)
Diese Art von Komplexität tritt häufig auf, wenn die Elemente eines Arrays durcheinander sind, d. h. sie sind weder in absteigender noch in aufsteigender Reihenfolge angeordnet.

Raumkomplexität – Space Complexity
Die Raumkomplexität wird 0(1), wenn eine zusätzliche Variable implementiert wird.

Best-Case-Komplexität – Best Case Complexity
Wenn ein Array keine Sortierung erfordert, ist die Anzahl der Durchläufe der äußeren Schleife n. Andererseits bleibt die innere Schleife inaktiv und führt keine Durchläufe aus. Dies bedeutet, dass die Anzahl der Vergleiche n beträgt, was zu einer linearen Komplexität führt.

Analyse der Zeitkomplexität

Es lässt sich zwar nicht leugnen, wie effizient die Einfügesortierung ist, aber wenn man der Einfügesortierung ein bereits sortiertes Array vorgibt, führt der Algorithmus immer noch die anderen für die Schleife aus. Dies erfordert n Schritte zum Sortieren eines Arrays mit den n Elementen, die bereits sortiert waren, was die Zeitkomplexität im besten Fall zu einer linearen n-Funktion macht.

Ein unsortiertes Array benötigt ein Element für den Vergleich mit anderen Elementen, d. h. jedes Element von n wird mit anderen n Elementen verglichen. Es wäre auch hilfreich, andere ähnliche Algorithmen wie Quick Sort, Merge Sort oder Selection Sort zu analysieren und ihre jeweilige Komplexität abzuschätzen.