Java Entwickler Experte
Insertion sort – Einfügungssortierung in Java
Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten benötigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erklären und sie in Java programmieren. Bislang haben wir die folgenden Sortieralgorithmen behandelt:
In diesem Artikel erfährst du:
- Sortieralgorithmen: eine Einführung in das Sortieren von Daten,
- Bubble sort – Blasen-Sortierung,
- Comb sort – Kamm-Sortierung,
- Big O Notation: Analyse der Komplexität von Algorithmen,
- Selection sort – triedenie výberom.
Heute werden wir uns die Einfügungssortierung – Insertion sort ansehen.
Insertion sort
Insertion Sort ist ein einfacher und intuitiver Algorithmus zum Sortieren eines Arrays oder einer Liste von Elementen. Er funktioniert ähnlich wie die Methode, mit der Menschen Spielkarten auf ihrer Hand sortieren. Sie halten ihre erhaltenen Karten sortiert und legen jede neue Karte, die sie erhalten, an ihren Platz, um ihre relative Reihenfolge beizubehalten.
Insertion sort vs selection, quick, merge sort
Insertion Sort wird oft als Teil von komplexeren Sortieralgorithmen verwendet (z.B. für kleine Teilmengen in Quick Sort oder Merge Sort), da seine Leistung für kleine Datensätze gut ist. Im Vergleich zu Selection Sort, das wir beim letzten Mal besprochen haben, bietet es einen stabilen Algorithmus.
Insertion sort algoritmus – Funktionsprinzip
Der Algorithmus beginnt mit der Aufteilung des Eingabevektors in einen sortierten und einen unsortierten Teil. Das erste Element des Arrays wird automatisch als sortiert betrachtet und die restlichen Elemente müssen noch sortiert werden. Für jedes Element im unsortierten Teil (vom zweiten bis zum letzten Element des Arrays) wird dieses Element ausgewählt und an der richtigen Stelle in den sortierten Teil des Arrays eingefügt, so dass der sortierte Teil weiterhin geordnet ist. Bei diesem Schritt wird das ausgewählte Element mit den anderen Elementen im sortierten Teil verglichen und die Elemente werden neu angeordnet, um Platz für das ausgewählte Element zu schaffen. Das Umordnen kann vermieden werden, wenn wir einen Listen-Datentyp anstelle eines Arrays wählen.
Anschließend werden wir ein praktisches Beispiel in Java-Code zeigen.
Vorteile des Sortieralgorithmus Insertion
- Leicht zu verstehen und umzusetzen,
- effizient für kleine Datensätze oder nahezu geordnete Arrays,
- geeignet für eingehende Elemente, die kontinuierlich sortiert werden müssen,
- benötigt keinen zusätzlichen Speicher für die Sortierung,
- stabil.
Nachteil des Sortieralgorithmus Insertion
- Die Zeitkomplexität ist jedoch immer noch O(n²), was ihn zu einem langsamen Algorithmus für einen großen Datensatz macht.
Intensität der Einfügezeit
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Insertion sort | einbetten. | O(n²) | O(n²) | n | O(1) | Ja |
Insertion sort Animation, Visualisierung, gif
Die Visualisierung der Insertion sort sieht wie folgt aus:
Quelle: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Eine Animation des Algorithmus findest du z.B. auf Toptal. Es gibt 8 Arten von Algorithmen, du kannst die Animation auch rückwärts abspielen. Auf dieser Seite kannst du die Schritte des Algorithmus durchlaufen, so dass diu den Zeitaufwand des Algorithmus überprüfen kannst.
Insertion sort Implementierung, Java-Code
Wir werden nun eine einfache Implementierung des Insertion-Sortieralgorithmus in Java zeigen.
InsertionSort.java
package sorting;
public class InsertionSort {
private int key, j;
public void sort(int data[])
{
// Start with 2nd element, as 1st is considered to be sorted
for (int i = 1; i < data.length - 1; i++) {
System.out.println(i + ". iteration (key = " + data[i] + ")");
// Element that needs to be inserted into sorted part
key = data[i];
j = i - 1;
// Move all elements > key one position to the right
while (j >= 0 && key < data[j]) {
data[j + 1] = data[j];
j--;
}
// Insert the key in its correct spot
data[j + 1] = key;
printArray(data);
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}
Main.java
import sorting.InsertionSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
InsertionSort insertionSort = new InsertionSort();
System.out.print("Input: ");
insertionSort.printArray(dataToSort);
insertionSort.sort(dataToSort);
System.out.print("Sorted: ");
insertionSort.printArray(dataToSort);
}
}Die Ausgabe dieses Beispiels ist:
Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausführen kannst. Lade den Java Insertion Sort Code herunter.
Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.
