Das Sortieren von Arrays ist eine der am häufigsten ausgeführten Operationen, die ein Java-Anfänger beherrschen sollte. Hierbei kommt oft Insertion Sort – das Sortieren durch Einfügen – zum Einsatz. Arrays sind zwar nicht immer die bequemste Art, Daten zu ordnen, und dies gilt vor allem für kleine Zahlen, aber das Konzept hinter der Array-Sortierung hat vielfältige Anwendungsmöglichkeiten bei komplexer Software und in der Data Science.
In diesem Beitrag werden wir einen genaueren Blick darauf werfen, was Insertion Sort – also Sortieren durch Einfügen – ist. Wir haben einige Beispiele und Übungsaufgaben für dich, damit du dieses Konzept vollständig verstehst.
Was ist Insertion Sort?
Insertion Sort ist ein Algorithmus, den Entwickler verwenden, um eine Menge von kleinen Zahlen zu sortieren. Er unterteilt alle Werte in zwei Stapel – einen sortierten und einen unsortierten. Eine nach der anderen werden die Zahlen im „unsortierten“ Stapel ausgewählt und in die richtige Reihenfolge gebracht.Schauen wir uns die Eingabe und die Ausgabe von Insertion Sort genauer an:
Eingabe: Ein Array A mit unsortierten numerischen Elementen: A[0, 1, n, n-2...].
Ausgabe: Ein Array mit denselben Zahlen, aber vollständig sortiert. Dieses wird üblicherweise als B bezeichnet: B[0]B[1]...B[n-1].
Es gibt eine Handvoll Möglichkeiten, das Sortieren durch Einfügen einzusetzen – hier die beliebtesten:
Hinweis: Wenn du ein leeres Array oder ein Singleton hast, werden diese standardmäßig als sortiert betrachtet.
Sortieren durch Einfügen – Die Theorie
Bevor wir den Code hinter Insertion Sort unter die Lupe nehmen, wollen wir den Algorithmus erstmal in einfacher Sprache formulieren. Da wir den Code für das Sortieren in aufsteigender Reihenfolge zeigen werden, ist es sinnvoll, den Algorithmus in diesem Beitrag Schritt für Schritt zu erklären.
Schritt 1. Iteriere zwischen arr[1] und arr[n], wobei n ein numerischer Wert ist, der normalerweise kleiner als 10 ist. <
span class="text-bold">Schritt 2. Vergleiche das gewählte Element (als key bezeichnet) mit der Methode sort() mit der vorherigen Zahl in der Folge.
Schritt 3. Wenn alle Elemente kleiner sind als ihre Nachfolger, wiederhole den Vergleich, bis ein größerer Wert gefunden wird.
Schritt 4. Vertausche einen größeren Wert mit der Position hinter dem kleineren, um eine geordnete Folge zu erhalten.
Schritt 5. Wiederhole den Vorgang, bis eine sortierte Folge herauskommt.
Primitive Arrays sortieren
Da es sich bei dem Algorithmus um eine der einfachsten Java-Operationen handelt, sollten auch absolute Anfänger keine großen Schwierigkeiten haben, ihn zu implementieren. Hier findest du eine Schritt-für-Schritt-Anleitung zum Sortieren eines Arrays:
1. Ein Array für die Sortierung deklarieren
Lass uns zunächst eine Folge mit Werten erstellen, die wir später mit Java anzeigen wollen. Damit du Insertion Sort nutzen kannst, musst du ein Array anlegen. Verwende dazu int[]
int[] arrayA = {10, 14, 20, 30};
2. Verwende sort_arr, um den Algorithmus zu implementieren
Die sort_arr-Methode ist eine der gebräuchlichsten Methoden zur Implementierung von Insertion Sort. In der Praxis sieht das so aus:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Erstelle eine Schleife und einen Iterator
Durch die Verwendung einer Schleife im Algorithmus für Insertion Sort muss der Entwickler die Logik nicht für jedes Element wiederholen. Auch wenn das Erstellen von Schleifen komplex erscheint, ist es tatsächlich ganz einfach – hier ein Beispiel:
for(int i=0; i< sort_arr.length; ++i){
Da du nun eine funktionierende Schleife hast, kannst du einen Iterator erstellen, der alle Elemente in der gewünschten Reihenfolge sortiert. Von nun an werden wir den Iterator als „j“ bezeichnen.
int j = i;
4. Eine „while“-Schleife erstellen
Beim Insertion-Sort-Algorithmus ist eine „while“-Schleife für ein neues, sortiertes Array unerlässlich. Um es für eine aufsteigende Sortierung durch Einfügen einzurichten, muss der Entwickler zwei Bedingungen erfüllen:
Der Wert, der j zugewiesen wird, muss größer als 0 sein
Der Wert, der j-1 zugewiesen wird, muss größer sein als der j-Index
Sobald beide Bedingungen in der while-Schleife wahr sind, ist der Schlüsselwert des Arrays gleich dem Index j.
5. Das Array sortieren
Nachdem Sie die while-Schleife eingerichtet haben, werden die Werte j und j-1 so lange vertauscht, bis eine oder beide Bedingungen in der while-Schleife nicht mehr erfüllt sind. In ähnlicher Weise wird die Sortierung für jeden Wert in der for-Schleife wiederholt, bis auch die Bedingungen der for-Schleife nicht mehr erfüllt sind.
Hier sehen Sie, wie Insertion Sort in der Praxis funktioniert:
Es ist durchaus wichtig, die Mathematik hinter Insertion Sort zu verstehen, aber in der realen Software-Entwicklung wirst du wesentlich mehr ArrayLists sortieren als Folgen in primitiven Arrays.
Hier findest du eine Schritt-für-Schritt-Anleitung zum Sortieren einer ArrayList:
Erstelle eine neue Klasse Element für die Elemente, die zur Sammlung gehören.
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
Innerhalb einer Sammlung gibt es eine compareTo()-Methode – wir werden diese verwenden, um die IDs zweier Elemente zu vergleichen.
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Wende den Algorithmus an und erstelle ein paar Schleifen, um die Objekte in einer ArrayList zu sortieren, anstatt sie zu vergleichen.
public static void insertionSortArrayList(List<element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
Du kannst der ArrayList auch weitere Elemente hinzufügen, wie unten gezeigt:
List<element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// To use insertion sort, shuffle the values
Collections.shuffle(list);
Zeit für die Sortierung:
// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Display a sorted array
list.forEach(e -> System.out.print(e.getId() + ", "));
Vergleichen wir nun die Eingabe und die Ausgabe, um sicherzustellen, dass wir keine Fehler gemacht haben. Hier ist der Vergleich der Folge, die wir als Beispiel verwendet haben.
Jetzt, wo wir diesen Sortieralgorithmus durchschaut haben, ist es an der Zeit, deine Theorie- und Praxiskenntnisse auf die Probe zu stellen.
Theorie-Quiz 1
Du erhältst ein Array [1, 4, 6, 8] und fügst diesem ein neues Element n = 7 hinzu. Wie viele Vergleiche musst du durchführen, um eine sortierte Zahlenfolge zu erhalten? Gib den Endwert des Index n im Array an.
Theorie-Quiz 2
Bei einem Vorstellungsgespräch bittet dich ein Teamleiter zu beweisen, dass Insertion Sort eine ineffiziente Methode ist. Gegeben sei die Zahlenfolge [0, 3, 6, 8, 9]; wie muss die Reihenfolge der Eingabefolge sein, um die für die Sortierung erforderliche Laufzeit zu maximieren?
Übungsaufgabe
Sortiere das Array [0, 1, 4, 5, 2, 3, 7, 9, 8] in aufsteigender Reihenfolge mit Insertion Sort für Java.
Fazit
Die größte Herausforderung beim Insertion Sort ist es, den Vorgang zu verstehen. Wenn du einmal den Dreh raus hast, ist das Umsetzen der Vorlage in Code ein Kinderspiel. Wenn du fleißig übst und die jeweiligen Übungsaufgaben wiederholst, wirst du die Geschwindigkeit deines Insertion Sort schnell verbessern.
Oleksandr became interested in programming at school, and he wrote games. Later, this hobby grew into professional development. Af ...
[Komplette Biografie lesen]
Schauen wir uns die Eingabe und die Ausgabe von Insertion Sort genauer an:
GO TO FULL VERSION