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 verringern Sie nach und nach den Abstand zwischen ihnen. Die Shell-Sortierung übersteigt die durchschnittliche FallzeitplexMöglichkeit der Einfügesortierung durch Vergleich und Austausch weit entfernter Elemente.

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.

Die folgendenwing GIF zeigt eine Demonstration der Shell-Sortierung. In dieser Demo werden der rot und der blau angezeigte Wert basierend auf der Einfügesortierung verglichen und vertauscht. Dann verringert sich das Intervall und die Shell-Sortierung initiiert die Einfügungssortierung in den fast sortierten Daten.

Shell Sort funktioniert

Funktionsweise des Shell-Sort-Algorithmus

Schauen wir uns mal ein Follo anwing Beispiel eines Shell-Sortieralgorithmus. In diesem Beispiel werden wir Folgendes sortierenwing Array mit Shell-Sortierung:

Funktionsweise des Shell-Sort-Algorithmus

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}.

Funktionsweise des Shell-Sort-Algorithmus

Schritt 3) Jetzt werden diese Unterlisten mithilfe der Einfügungssortierung sortiert, wobei eine temporäre Variable verwendet wird, um beide Zahlen zu vergleichen und entsprechend zu sortieren.

Das Array würde wie folgt aussehenwing nach dem Austausch von Operationen-

Funktionsweise des Shell-Sort-Algorithmus

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}

Funktionsweise des Shell-Sort-Algorithmus

Anschließend werden diese Unterlisten mithilfe der Einfügungssortierung sortiert. Nach dem Vergleich und Austausch der ersten Unterliste wäre das Array das Folgendewing.

Funktionsweise des Shell-Sort-Algorithmus

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

Funktionsweise des Shell-Sort-Algorithmus

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.

Following ist die schrittweise Darstellung der Einfügesortierung.

Funktionsweise des Shell-Sort-Algorithmus

Funktionsweise des Shell-Sort-Algorithmus

Funktionsweise des Shell-Sort-Algorithmus

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-

Funktionsweise des Shell-Sort-Algorithmus

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

Beispiel für eine Shell-Sortierung 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 Complexity-Analyse

Time Complexität von Shell Sort

Die Zeit complexDie Größe des Shell-Sortieralgorithmus ist O(n^2). Die Begründung lautet wie folgt:

Im besten Fall entspricht die Gesamtzahl der Tests für alle Intervalle, in denen das Array zuvor angeordnet war, log n. So die complexity wäre 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 Zeit complexities wären

  1. Best Case complexität: O(n*log n)
  2. Durchschnittlicher Fall complexität: O(n*log n)
  3. Im schlimmsten Fallplexität: O(n^2)

Die Laufzeit complexDie Qualität der Shell-Sortierung hängt stark von den verwendeten Lückeninkrementsequenzen ab. Allerdings ist die beste Inkrementreihenfolge für die Shell-Sortierung noch unbekannt.

Shell Sort Space Complexity

Bei dieser Vergleichssortierung benötigen wir keinen zusätzlichen Hilfsraum. So ist der Raum complexDie Funktionalität dieser Art von Algorithmus ist O(1).