Einfügungssortierung in Java

1. Übersicht

In diesem Tutorial werden wir den Insertion Sort-Algorithmus diskutieren und einen Blick auf seine Java-Implementierung werfen .

Die Einfügesortierung ist ein effizienter Algorithmus zum Bestellen einer kleinen Anzahl von Artikeln. Diese Methode basiert auf der Art und Weise, wie Kartenspieler eine Hand von Spielkarten sortieren.

Wir beginnen mit einer leeren linken Hand und den auf den Tisch gelegten Karten. Wir nehmen dann jeweils eine Karte vom Tisch und legen sie an der richtigen Stelle in der linken Hand ein. Um die richtige Position für eine neue Karte zu finden, vergleichen wir sie von rechts nach links mit dem bereits sortierten Kartensatz in der Hand.

Beginnen wir mit dem Verständnis der Algorithmusschritte in Pseudocode-Form.

2. Pseudocode

Wir werden unseren Pseudocode für die Einfügesortierung als eine Prozedur namens INSERTION-SORT präsentieren , die als Parameter ein Array A [1 .. n] von n zu sortierenden Elementen verwendet. Der Algorithmus sortiert das Eingabearray an Ort und Stelle (indem er die Elemente innerhalb des Arrays A neu anordnet).

Nach Abschluss der Prozedur enthält das Eingabearray A eine Permutation der Eingabesequenz, jedoch in sortierter Reihenfolge:

INSERTION-SORT(A) for i=2 to A.length key = A[i] j = i - 1 while j > 0 and A[j] > key A[j+1] = A[j] j = j - 1 A[j + 1] = key

Lassen Sie uns kurz auf den obigen Algorithmus eingehen.

Der Index i gibt die Position des aktuellen Elements im zu verarbeitenden Array an.

Wir beginnen mit dem zweiten Element, da per Definition ein Array mit einem Element als sortiert betrachtet wird. Das Element am Index i wird als Schlüssel bezeichnet . Sobald der Schlüssel vorhanden ist, befasst sich der zweite Teil des Algorithmus mit dem Finden des richtigen Index. Wenn der Schlüssel kleiner als der Wert des Elements am Index j ist , bewegt sich der Schlüssel um eine Position nach links. Der Prozess wird fortgesetzt, bis wir ein Element erreichen, das kleiner als der Schlüssel ist.

Es ist wichtig zu beachten, dass vor dem Start der Iteration zum Finden der korrekten Position des Schlüssels am Index i das Array A [1 .. j - 1] bereits sortiert ist .

3. Imperative Implementierung

Für den imperativen Fall schreiben wir eine Funktion namens insertionSortImperative , die als Parameter ein Array von Ganzzahlen verwendet. Die Funktion beginnt ab dem zweiten Element mit der Iteration über das Array.

Zu jedem Zeitpunkt während der Iteration können wir uns dieses Array als logisch in zwei Teile unterteilt vorstellen. Die linke Seite ist die sortierte und die rechte Seite enthält die noch nicht sortierten Elemente.

Ein wichtiger Hinweis hierbei ist, dass wir nach dem Finden der richtigen Position, an der wir das neue Element einfügen, die Elemente nach rechts verschieben (und nicht tauschen) , um einen Platz dafür freizugeben.

public static void insertionSortImperative(int[] input) { for (int i = 1; i 
    
     = 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; } }
    

Als nächstes erstellen wir einen Test für die obige Methode:

@Test public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() { int[] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Der obige Test beweist, dass der Algorithmus das Eingabearray in aufsteigender Reihenfolge korrekt sortiert .

4. Rekursive Implementierung

Die Funktion für den rekursiven Fall heißt insertionSortR ecursive und akzeptiert als Eingabe ein Array von Ganzzahlen (wie für den imperativen Fall).

Der Unterschied zum imperativen Fall (trotz der Tatsache, dass er rekursiv ist) besteht darin, dass eine überladene Funktion mit einem zweiten Argument aufgerufen wird, das der Anzahl der zu sortierenden Elemente entspricht.

Wenn wir das gesamte Array sortieren möchten, übergeben wir eine Anzahl von Elementen, die seiner Länge entsprechen:

public static void insertionSortRecursive(int[] input) { insertionSortRecursive(input, input.length); }

Der rekursive Fall ist etwas schwieriger. Der Basisfall tritt auf, wenn wir versuchen, ein Array mit einem Element zu sortieren. In diesem Fall tun wir nichts.

Alle nachfolgenden rekursiven Aufrufe sortieren einen vordefinierten Teil des Eingabearrays - beginnend mit dem zweiten Element bis zum Ende des Arrays:

private static void insertionSortRecursive(int[] input, int i) { if (i <= 1) { return; } insertionSortRecursive(input, i - 1); int key = input[i - 1]; int j = i - 2; while (j>= 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; }

Und so sieht der Aufrufstapel für ein Eingabearray mit 6 Elementen aus:

insertionSortRecursive(input, 6) insertionSortRecursive(input, 5) and insert the 6th item into the sorted array insertionSortRecursive(input, 4) and insert the 5th item into the sorted array insertionSortRecursive(input, 3) and insert the 4th item into the sorted array insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

Sehen wir uns auch den Test dafür an:

@Test public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() { int[] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Der obige Test beweist, dass der Algorithmus das Eingabearray in aufsteigender Reihenfolge korrekt sortiert .

5. Zeit- und Raumkomplexität

Die Ausführungszeit der INSERTION-SORT- Prozedur beträgt O (n ^ 2) . Für jedes neue Element durchlaufen wir den bereits sortierten Teil des Arrays von rechts nach links, um die richtige Position zu finden. Dann fügen wir es ein, indem wir die Elemente um eine Position nach rechts verschieben.

Der Algorithmus wird an Ort und Stelle sortiert, sodass seine Raumkomplexität O (1) für die imperative Implementierung und O (n) für die rekursive Implementierung beträgt .

6. Fazit

In diesem Tutorial haben wir gesehen, wie die Einfügesortierung implementiert wird.

Dieser Algorithmus ist nützlich, um eine kleine Anzahl von Elementen zu sortieren. Es wird ineffizient, wenn Eingabesequenzen mit mehr als 100 Elementen sortiert werden.

Beachten Sie, dass es trotz seiner quadratischen Komplexität ohne zusätzlichen Platz sortiert wird, wie dies bei der Zusammenführungssortierung der Fall ist .

Der gesamte Code konnte auf GitHub gefunden werden.