Shellsort-Algorithmus mit Beispiel

Was ist Shellsort?

Shellsort, auch Shell-Verfahren genannt, ist ein effizienter, auf Vergleichen basierender Sortieralgorithmus, der direkt im Speicher durchgeführt wird. Benannt nach Donald Shell, der die Idee 1959 vorstellte, stellt er eine verallgemeinerte Erweiterung des Insertionsort-Algorithmus dar, die dessen quadratisches Verhalten bei verstreuten Daten überwindet.

Die Grundidee besteht darin, weit voneinander entfernte Elemente zu gruppieren, jede Gruppe mithilfe des Einfügesortierverfahrens zu sortieren und den Abstand schrittweise zu verringern, bis er eins beträgt. Dann ist das Array nahezu sortiert.

Diese Lücke, das Intervall, folgt einer gewählten Sequenz, wie beispielsweise Shells Original, Knuths, Hibbards oder Sedgewicks. Shells Original ist n/2, n/4, ..., 1.

Shell-Sortieralgorithmus

Schritt 1) Initialisiere den Intervallwert h = n/2, wobei n die Größe des Arrays ist.

Schritt 2) Platziere alle Elemente innerhalb eines Abstands des Intervalls h in einer Unterliste.

Schritt 3) Sortieren Sie jede Teilliste mithilfe des Einfügesortierverfahrens.

Schritt 4) Setze ein neues Intervall h = h/2.

Schritt 5) Falls h > 0, kehre zu Schritt 2 zurück. Andernfalls gehe zu Schritt 6.

Schritt 6) Das resultierende Array ist nun vollständig sortiert.

So funktioniert die Shell-Sortierung

Beim Einfügesortierverfahren werden Elemente jeweils nur um eine Position verschoben. Shellsort hingegen teilt das Array anhand des Intervalls in weit auseinanderliegende Teillisten auf und wendet das Einfügesortierverfahren auf jede Teilliste an.

Mit abnehmendem Intervall wächst die Größe der Teilliste. Da frühere Durchläufe die Daten nur teilweise sortiert hinterlassen, benötigen kleinere Intervalle deutlich weniger Vertauschungen als die Ausführung von Sortieren durch Einfügen von Grund auf. Die folgende Abbildung veranschaulicht einen Shellsort-Durchlauf.

Funktionsweise des Shellsort-Algorithmus mit Beispiel

Sortieren wir das untenstehende Array mit Shell Sort.

Schritt 1) Die Arraygröße beträgt 8, daher ist der Anfangsintervallwert h = 8/2 = 4.

Schritt 2) Gruppiere Elemente im Abstand von vier Positionen. Teillisten: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Schritt 3) Sortiere jede Teilliste mit dem Einfügesortierverfahren. Eine temporäre Variable speichert den jeweils eingefügten Wert während der Verschiebung der Elemente. Nach dem Vertauschen sieht das Array folgendermaßen aus.

Schritt 4) Verringere das Intervall. Das neue Intervall ist h = 4/2 = 2.

Schritt 5) Da 2 > 0, kehre zu Schritt 2 zurück und gruppiere Elemente, die zwei Positionen voneinander entfernt sind: {1, 5, 8, 7} und {4, 2, 6, 3}.

Sortiere die erste Teilliste. Das Array sieht dann so aus:

Nach dem Sortieren der zweiten Teilliste:

Verringern Sie das Intervall erneut auf h = 2/2 = 1. Mit einem Abstand von eins führt Shell Sort einen letzten Insertionsort-Durchlauf über das gesamte Array durch, wie unten gezeigt.

Schritt 6) Teilt man das Intervall erneut, erhält man 0. Das Array ist nun vollständig sortiert:

Pseudo-Code für Shell Sort

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > 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

Der Shellsort findet sich auch heute noch in modernen Systemen, in denen es auf Speicherplatz oder Einfachheit ankommt.

• Das Linux-Kernel verwendet Shell Sort an Stellen, an denen die Vermeidung eines Aufrufstapels wichtig ist.
• Die eingebettete C-Bibliothek uClibc verwendet Shell Sort, um den Speicherverbrauch gering zu halten.
• bzip2 verwendet Shell Sort, um tiefe Rekursionen beim Blocksortieren zu vermeiden.
• Eingebettete Firmware bevorzugt Shell Sort für kleine Datensätze, bei denen Rekursion eingeschränkt ist.

Vor- und Nachteile der Schalensortierung

Shell-Sort-Komplexitätsanalyse

Zeitliche Komplexität der Shell-Sortierung

Die Zeitkomplexität des Shellsort-Algorithmus hängt von der verwendeten Lückensequenz ab.

Im besten Fall, wenn das Array bereits nahezu vollständig angeordnet ist, benötigt jeder Durchlauf nur eine logarithmische Anzahl von Tests, was O(n log n) ergibt.

Im schlimmsten Fall ist das Array so angeordnet, dass die Elemente die maximale Anzahl an Vergleichen benötigen, und die letzte Inkrementierung dominiert bei O(n^2) mit Shells ursprünglicher Sequenz.

1. Beste-Case-Komplexität: O(n log n)
2. Die durchschnittliche Komplexität liegt zwischen O(n log n) und O(n^(4/3)), abhängig von der Lückensequenz.
3. Worst-Case-Komplexität: O(n^2) mit Shells ursprünglicher Sequenz

Die beste universelle Gap-Sequenz ist noch immer eine offene Forschungsfrage, obwohl sich die Sequenzen von Sedgewick und Ciura in der Praxis gut bewähren.

Komplexität des Shell-Sortierraums

Shell Sort benötigt keine Hilfsarrays, daher ist die Speicherkomplexität unabhängig von der Eingabegröße O(1), was einer seiner größten praktischen Vorteile ist.

Häufig gestellte Fragen