Shell-Sortieralgorithmus mit BEISPIEL

Was ist Shell Sort?

Die Shell-Methode oder Shell-Sortierung in der Datenstruktur ist ein effizienter Sortieralgorithmus für den direkten Vergleich. Es ist nach Donald Shell benannt, als er 1959 die ursprüngliche Idee vorschlug. Die Shell-Sortierung ist eine verallgemeinerte Erweiterung des Einfügungssortierungsalgorithmus.

Die Grundidee dieses Sortieralgorithmus besteht darin, weit auseinander liegende Elemente zu gruppieren und entsprechend zu sortieren. Dann wird der Abstand zwischen ihnen schrittweise verringert. Shellsort überwindet die durchschnittliche Zeitkomplexität des Insertionsorts, indem weit auseinander liegende Elemente verglichen und ausgetauscht werden.

Diese als Intervall bezeichnete Lücke wird entsprechend einigen optimalen Lückensequenzen reduziert. Auch die Laufzeit der Shell-Sortierung hängt von diesen Sequenzen ab. Es gibt mehrere Lückensequenzen, wie zum Beispiel die Originalsequenz von Shell, die Formel von Knuth, die Inkremente von Hibbard usw. Die ursprüngliche Lückensequenz von Shell ist – n/2, n/4, n/8, ……….1

Shell-Sortieralgorithmus

Die Schritte oder das Verfahren für den Shell-Sortieralgorithmus sind wie folgt:

Schritt 1) Initialisieren Sie den Intervallwert, h = n/2. (In diesem Beispiel ist n die Größe des Arrays)

Schritt 2) Fügen Sie alle Elemente im Abstand des Intervalls h in eine Unterliste ein.

Schritt 3) Sortieren Sie diese Unterlisten mithilfe der Einfügungssortierung.

Schritt 4) Neues Intervall einstellen, h=h/2.

Schritt 5) Wenn h>0, fahren Sie mit Schritt 2 fort. Andernfalls fahren Sie mit Schritt 6 fort.

Schritt 6) Die resultierende Ausgabe ist das sortierte Array.

So funktioniert die Shell-Sortierung

Bei der Einfügesortierung werden Elemente jeweils nur um eine Position verschoben. Im Gegensatz dazu unterteilt die Shell-Sortierung das Array basierend auf dem Intervallwert in kleinere Teile und führt für diese Teile eine Einfügungssortierung aus.

Allmählich nimmt der Intervallwert ab und die Größe der geteilten Stücke nimmt zu. Da die Teile vorher einzeln sortiert werden, erfordert das Zusammenführen dieser Teile weniger Schritte als das Sortieren durch Einfügen.

Das folgende GIF zeigt eine Demonstration von Shellsort. In dieser Demo werden die rot und blau angezeigten Werte verglichen und basierend auf Insertionsort vertauscht. Dann verringert sich das Intervall und Shellsort leitet Insertionsort in diesen fast sortierten Daten ein.

Funktionsweise des Shell-Sort-Algorithmus

Sehen wir uns das folgende Beispiel eines Shellsort-Algorithmus an. In diesem Beispiel sortieren wir das folgende Array mit Shellsort:

Schritt 1) Hier beträgt die Array-Größe 8. Somit beträgt der Intervallwert h = 8/2 oder 4.

Schritt 2) Jetzt speichern wir alle Elemente im Abstand von 4. In unserem Fall sind die Unterlisten: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Schritt 3) Jetzt werden diese Unterlisten mithilfe der Insertionsort-Methode sortiert. Dabei wird eine temporäre Variable verwendet, um die beiden Zahlen zu vergleichen und entsprechend zu sortieren.

Nach den Vertauschungsvorgängen sähe das Array wie folgt aus:

Schritt 4) Jetzt verringern wir den Anfangswert des Intervalls. Das neue Intervall ist h=h/2 oder 4/2 oder 2.

Schritt 5) Da 2>0 ist, gehen wir zu Schritt 2, um alle Elemente im Abstand von 2 zu speichern. Zu diesem Zeitpunkt sind die Unterlisten:

{1, 5, 8, 7}, {4, 2, 6, 3}

Anschließend werden diese Unterlisten per Insertionsort sortiert. Nach dem Vergleichen und Vertauschen der ersten Unterliste sähe das Array wie folgt aus.

Nach dem Sortieren der zweiten Unterliste sieht das ursprüngliche Array wie folgt aus:

Andererseits wird das Intervall verkürzt. Jetzt ist das Intervall h=h/2 oder 2/1 oder 1. Daher verwenden wir den Einfügungssortierungsalgorithmus, um das geänderte Array zu sortieren.

Nachfolgend sehen Sie die schrittweise Vorgehensweise beim Insertionsort.

Das Intervall wird erneut durch 2 geteilt. Zu diesem Zeitpunkt ist das Intervall 0. Wir fahren also mit Schritt 6 fort.

Schritt 6) Da das Intervall 0 ist, wird das Array nach dieser Zeit sortiert. Das sortierte Array ist-

Pseudocode

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
    a[j] = a[j - interval];
a[j] = temp;
End

Shell-Sortierprogramm in C/C++

Eingang:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Ausgang:

Sorted Output:

1 2 3 4 5 6 7 8

Shell Sort Beispiel in Python

Eingang:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Ausgang:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Anwendungen von Shell Sort

Hier sind wichtige Anwendungen von Shell Sort:

Shell-Sortierung wird in der verwendet Linux-Kernel weil es keinen Aufrufstapel verwendet.
Die uClibc-Bibliothek verwendet die Shell-Sortierung.
Der bzip2-Kompressor verwendet die Shell-Sortierung, um eine übermäßige Rekursion zu verhindern.

Vor- und Nachteile der Schalensortierung

Vorteile	Nachteile
Es ist kein Stack-Aufruf erforderlich.	Nicht effizient für große Array-Größen.
Einfache Implementierung.	Ineffizient für weit verbreitete Elemente.
Effizient für Elemente mit geringerem Abstand.

Shell-Sort-Komplexitätsanalyse

Zeitliche Komplexität der Shell-Sortierung

Die Zeitkomplexität des Shellsort-Algorithmus beträgt O(n^2). Die Begründung lautet wie folgt:

Im besten Fall ist die Gesamtzahl der Tests für alle Intervalle, in denen das Array zuvor angeordnet wurde, gleich log n. Somit wäre die Komplexität O(n*log n).

Nehmen wir für den schlimmsten Fall an, dass das Array so aufgebaut ist, dass die Elemente die höchste Anzahl an Vergleichen erfordern. Dann werden alle Elemente erst in der letzten Iteration verglichen und vertauscht. Daher sind für das letzte Inkrement insgesamt O(n^2) Vergleiche erforderlich.

Zusammenfassend lässt sich sagen, dass die zeitliche Komplexität

Beste Fallkomplexität: O(n*log n)
Durchschnittliche Fallkomplexität: O(n*log n)
Komplexität im schlimmsten Fall: O(n^2)

Die Laufzeitkomplexität von Shellsort hängt stark von den verwendeten Gap-Inkrementsequenzen ab. Die beste Inkrementsequenz für Shellsort ist jedoch noch unbekannt.

Komplexität des Shell-Sortierraums

Bei dieser Vergleichssortierung benötigen wir keinen zusätzlichen zusätzlichen Speicherplatz. Daher beträgt die Speicherkomplexität dieser Art von Algorithmus O(1).

Du magst vielleicht: