Shell Sort

Shell Sort Beschreibung

Der Shell Sort oder auch Shellsort Algorithmus basiert auf Insertion Sort, ist jedoch das schnellere Verfahren. Das Grundprinzip ist es, Datenmengen in Teilmengen zu zerlegen und diese mit Insertion Sort zu sortieren. Dadurch erhältst Du bei jedem Iterationsschritt eine neue Grobsortierung. Die Teilmengen werden mit jedem Schritt kleiner, bis Du schließlich eine vollständig sortierte Liste bekommst.

Shell Sort Definition

Shell Sort Algorithmus

Wie Du bei Shellsort vorgehst, lässt sich am besten an einem Beispiel zeigen. Gegeben ist folgendes Array:

Das Grundprinzip bei Shellsort ist es, eine Datenmenge in kleinere Teilmengen zu zerteilen. Die Länge der Teilmenge bestimmt dabei die Laufzeit des Algorithmus mit – Du solltest die einzelnen Teilbereiche also weder zu groß noch zu klein wählen.

In diesem Beispiel werden die Längen 4, 2 und 1 gewählt.

1. Iteration

Im ersten Durchlauf wird das Array in zwei Arrays mit jeweils einer Länge von 4 geteilt. Diese schreibst Du am besten untereinander – das macht es übersichtlicher.

Jetzt sortierst Du die einzelnen Spalten nach dem Insertion Sort – also von oben nach unten. Dabei musst Du die 8 und die 2 und die 4 mit der 3 vertauschen.

Anschließend fügst Du die Teilbereiche wieder zu einem Array zusammen:

2. Iteration

Nun kommt der zweite Durchlauf, wobei diesmal die Länge 2 für die Teillisten gewählt wird. Auch diese Teillisten schreibst Du wieder untereinander und sortierst sie spaltenweise mit Insertion Sort.

Nach dem Sortieren erhältst Du folgendes Zwischenergebnis.

Dieses führst Du wieder zu einer Gesamtliste zusammen.

3. Iteration

Beim dritten Durchlauf wählst Du jetzt eine Länge von 1 für die einzelnen Teilbereiche. Anders gesagt: Du sortierst die übrige Liste einfach mit Insertion Sort. Da die Liste schon teilweise vorsortiert ist, dauert das Sortieren hier in der Regel nicht mehr allzu lange.

Als Ergebnis erhältst Du nach den letzten Vertauschungen die sortierte Liste:

Und fertig ist Dein sortiertes Array nach Shell Sort!

Shell Sort Vorgehensweise

Noch einmal kurz und knapp, wie gehst Du beim Shellsort Algorithmus vor:

• Lege die Länge für die Teilmengen/Intervalle fest
• Zerteile die unsortierte Datenmenge in Teilmengen und sortiere diese mit Insertion Sort
• Führe das Ganze so lange durch, bis die Datenmenge vollständig sortiert ist

Shell Sort Struktogramm

Wie könnte ein mögliches Struktogramm bei Shell Sort aussehen?

Abb. 1 Struktogramm für Shell Short

Shell Sort Komplexität

Bei der Komplexität von Shell Sort müssen die Laufzeit (Zeitkomplexität) und der zusätzlich benötigte Speicher (Platzkomplexität) betrachtet werden.

Shell Sort Laufzeit

Wie effizient Shell Sort ist, hängt stark von der Wahl der Länge der Teilmengen ab. Doch warum verwendet man überhaupt Shell Sort, wenn es sich dabei im Prinzip auch einfach nur um den Insertion Sort Algorithmus handelt? Durch die Grobsortierung des Shell Sort bekommst Du eine deutlich bessere Laufzeit als bei Insertion Sort.

Shell Sort Worst Case

Im Worst-Case, also bei einer eher schlecht gewählten Intervall-Länge, hat Shell Sort eine Laufzeit von O(n²),

Shell Sort Best Case

Sowohl im Best-Case als auch im Average-Case hat Shell Sort hingegen eine Laufzeit von O(n log n).

Shell Sort Platzkomplexität

Shellsort läuft in-place, also ohne zusätzlich benötigten Speicherplatz, ab. Somit ist die Platzkomplexität konstant und beträgt O(1).

Shell Sort – Weitere Begrifflichkeiten

Im Folgenden werden noch weitere wichtige Begriffe rund um Shellsort erläutert.

Shell Sort stabil – instabil

Durch das Unterteilen in Teilmengen und das Sortieren dieser Teillisten untereinander mit Insertion Sort, kann die ursprüngliche Reihenfolge bei gleichen Elementen nicht gewährleistet werden. Der Algorithmus ist also instabil.

Shell Sort vergleichsbasiert

Shell Sort ist ein vergleichsbasiertes Sortierverfahren, da immer zwei Elemente miteinander verglichen werden, um über ihre Anordnung in der Datenmenge zu entscheiden.

Shell Sort Parallelisierbarkeit

Im Gegensatz zum ursprünglichen Insertion Sort ist Shellsort parallelisierbar. Dafür lagerst Du die einzelnen Teilmengen im Grunde einfach auf Prozessoren aus. Dort werden die Daten parallel mit einem eigenen Shellsort sortiert. Anschließend fügst Du die sortierten Teilmengen wieder zu einer kompletten Liste zusammen, wobei die Daten noch mal abschließend sortiert werden.

Shell Sort Zusammenfassung

Das bisher Gelernte findest Du hier auf einem Blick zusammengefasst:

Insertion Sort vs. Shell Sort

Shell Sort basiert auf dem Insertion Sort Sortierverfahren, was dabei die Unterschiede sind, kannst Du der folgenden Tabelle entnehmen. Wichtig zu wissen ist noch, dass Shell Sort grundsätzlich entwickelt wurde, um die Ineffizienz des Insertion Sorts zu verbessern. Ziel war es also, die große Anzahl an Vergleichen zu reduzieren.

Shell Sort Java

Nun folgen noch zwei Code-Beispiele für eine mögliche Implementierung – in Java könnte das wie folgt aussehen:

import java.util.Arrays;

class ShellSort {

    // Elemente mit den Intervallen von n/2, n/4, n/8, ... neu anordnen
  void shellSort(int array[], int n) {
  for (int interval = n / 2; interval > 0; interval /= 2) {

    for (int i = interval; i < n; i += 1) {
        int temp = array[i];
        int j;
    
            for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
                array[j] = array[j - interval];
                }

            array[j] = temp;
            }
    }
  }

// Treibercode

public static void main(String args[]) {
    // zu sortierende Datenmenge eingeben
    int[] data = { 5, 2, 8, 4, 9, 7, 2, 3 };
    int size = data.length;
    ShellSort ss = new ShellSort();
    ss.shellSort(data, size);

    // Ausgabe hinzufügen
    System.out.println("Sortiertes Array: " " + Arrays.toString(data));
    }
}

Ausgabe:

Sortiertes Array: 2 2 3 4 5 7 8 9 

Shell Sort C

In C könnte Shell Sort hingegen so implementiert werden.

#include 
void shellSort(int array[], int n) {

    // Elemente mit den Intervallen von n/2, n/4, n/8, ... neu anordnen
    for (int interval = n / 2; interval > 0; interval /= 2) {
        
        for (int i = interval; i < n; i += 1) {
            int temp = array[i];
            int j;
        
            for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
            array[j] = array[j - interval];
            }

        array[j] = temp;
        }
    }
}

// Array ausgeben

void printArray(int array[], int size) {
    for (int i = 0; i < size; ++i) {
        printf("%d  ", array[i]);
        }

    printf("\n");
}

// Treibercode

int main() {

  int data[] = {5, 2, 8, 4, 9, 7, 2, 3};
  int size = sizeof(data) / sizeof(data[0]);
  shellSort(data, size);

  printf("Sortiertes Array: \n");
  printArray(data, size);
}