Shell Sort in Java

1. Einleitung

In diesem Tutorial beschreiben wir den Shell-Sortieralgorithmus in Java.

2. Die Shell-Sortierübersicht

2.1. Beschreibung

Beschreiben wir zunächst den Shell-Sortieralgorithmus, damit wir wissen, was wir implementieren möchten.

Die Shell-Sortierung basiert auf dem Insertion-Sortieralgorithmus und gehört zur Gruppe der sehr effizienten Algorithmen. Im Allgemeinen zerlegt der Algorithmus eine ursprüngliche Menge in kleinere Teilmengen, und dann wird jede dieser Mengen mithilfe der Einfügesortierung sortiert .

Es ist jedoch nicht einfach, wie die Teilmengen erstellt werden. Es werden keine benachbarten Elemente ausgewählt, um eine Teilmenge zu bilden, wie wir es erwarten könnten. Die Shell-Sortierung verwendet vielmehr das sogenannte Intervall oder die Lücke für die Erstellung von Teilmengen. Wenn wir zum Beispiel die Lücke I haben , bedeutet dies, dass eine Teilmenge die Elemente enthält, die I- Positionen voneinander entfernt sind.

Erstens sortiert der Algorithmus die Elemente, die weit voneinander entfernt sind. Dann wird die Lücke kleiner und engere Elemente werden verglichen. Auf diese Weise können einige Elemente, die sich nicht an der richtigen Position befinden, schneller positioniert werden, als wenn wir die Teilmengen aus den benachbarten Elementen erstellt hätten.

2.2. Ein Beispiel

Lassen Sie uns dies im Beispiel mit den Lücken 3 und 1 und der unsortierten Liste von 9 Elementen sehen:

Wenn wir der obigen Beschreibung folgen, haben wir in der ersten Iteration drei Teilmengen mit 3 Elementen (hervorgehoben durch dieselbe Farbe):

Nach dem Sortieren jeder Teilmenge in der ersten Iteration sieht die Liste folgendermaßen aus:

Wir können feststellen, dass die Elemente jetzt noch näher an den gewünschten Positionen liegen, obwohl wir noch keine sortierte Liste haben.

Schließlich müssen wir eine weitere Sortierung mit dem Inkrement von eins durchführen, und es handelt sich tatsächlich um eine einfache Einfügungssortierung. Die Anzahl der Verschiebungsvorgänge, die wir zum Sortieren einer Liste ausführen müssen, ist jetzt geringer als wenn wir nicht die erste Iteration durchgeführt hätten:

2.3. Auswahl der Lückensequenzen

Wie bereits erwähnt, bietet die Shell-Sortierung eine einzigartige Möglichkeit, Lückenfolgen auszuwählen. Dies ist eine schwierige Aufgabe, und wir sollten darauf achten, nicht zu wenige oder zu viele Lücken zu wählen. Weitere Details finden Sie in der Liste der am häufigsten vorgeschlagenen Lückensequenzen.

3. Implementierung

Schauen wir uns nun die Implementierung an. Wir werden die ursprüngliche Sequenz von Shell für Intervallinkremente verwenden:

N/2, N/4, …, 1 (continuously dividing by 2)

Die Implementierung selbst ist nicht zu komplex:

public void sort(int arrayToSort[]) { int n = arrayToSort.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arrayToSort[j - gap] > key) { arrayToSort[j] = arrayToSort[j - gap]; j -= gap; } arrayToSort[j] = key; } } }

Wir haben zuerst eine Lückensequenz mit einer for-Schleife erstellt und dann die Einfügesortierung für jede Lückengröße durchgeführt.

Jetzt können wir unsere Methode einfach testen:

@Test public void givenUnsortedArray_whenShellSort_thenSortedAsc() { int[] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort(input); int[] expected = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals("the two arrays are not equal", expected, input); }

4. Komplexität

Im Allgemeinen ist der Shell-Sortieralgorithmus bei mittelgroßen Listen sehr effizient . Die Komplexität ist schwer zu bestimmen, da sie stark von der Lückenfolge abhängt, die zeitliche Komplexität variiert jedoch zwischen O (N) und O (N ^ 2) .

Die Raumkomplexität im ungünstigsten Fall ist O (N) mit O (1) Hilfsraum.

5. Schlussfolgerung

In diesem Tutorial haben wir die Shell-Sortierung beschrieben und veranschaulicht, wie wir sie in Java implementieren können.

Wie üblich konnte der gesamte Code auf GitHub gefunden werden.