Shellsort

ShellSort ist ein von Donald L. Shell im Jahre 1959 entwickelter Sortieralgorithmus, der auf dem Sortieralgorithmus des direkten Einfügens (Insertionsort) basiert.

Prinzip

Der Gedanke, der hinter ShellSort steht, kann wie folgt beschrieben werden:

• Die Daten werden in eine zweidimensionale Matrix geschrieben
• Die Spalten der Matrix werden einzeln sortiert

Daraus resultiert eine grobe Sortierung. Dieser Schritt wird öfter wiederholt, wobei jeweils die Breite der Matrix verringert wird, bis die Matrix nur noch aus einer einzigen vollständig sortierten Spalte besteht.

ShellSort arbeitet instabil und in-place.

Beispiel

Zu sortieren sind die Zahlen: 2 5 3 4 3 9 3 2 5 4 1 3

Zuerst werden die Daten in eine Matrix mit 4 Spalten eingetragen und spaltenweise sortiert.

2 5 3 4      2 4 1 2
3 9 3 2  ->  3 5 3 3
5 4 1 3      5 9 3 4

Die sortierte 4-Spalten-Matrix wird nun in zwei Spalten aufgeteilt. Diese Spalten werden nun sortiert.

2 4      1 2
1 2      2 3
3 5  ->  3 4
3 3      3 4
5 9      3 5
3 4      5 9

Die sortierte 2-Spalten-Matrix wird nun in eine Spalte geschrieben und wieder sortiert.

1 2 2 3 3 4 3 4 3 5 5 9  ->  1 2 2 3 3 3 3 4 4 5 5 9

Implementierung

Java

Tatsächlich werden die Daten nicht in Form einer Matrix, sondern in Form eines eindimensionalen Feldes angeordnet. Die Spalten werden durch geschickte Indizierung gebildet. So bilden alle Elemente im Abstand h eine Zeile. Die Spalten werden per Insertionsort sortiert, da dieser Algorithmus von einer Vorsortierung der Daten profitieren kann.

void shellsort (int[] a, int n)
{   int i, j, k, h, t;
    int[] spalten = { 1, 4, 13, 41, 111, 271, 815, 1968, 4711, 11969, 27901, 84801,
                      213331, 543749, 1355339, 3501671, 8810089, 21521774,
                      58548857, 157840433, 410151271, 1131376761, 2147483647 };
    // finde den Index gerade groesser als n
    for ( k = 0; spalten[k] < n; k++ );
    // beginne mit den Spalten-Wert der gerade kleiner als n ist
    while ( --k >= 0 )
    {   h = spalten[k];
        // Verwende InsertionSort auf die "Spalten"
        for ( i = h; i < n; i++ )
        {   t = a[i];
            j = i;
            while ( j >= h && a[j - h] > t )
            {   a[j] = a[j - h];
                j = j - h;
            }
            a[j] = t;
        }
    }
} 

Pascal und Delphi

Sortiert wird ein Array mit dem Namen f, das genau N Elemente des Typs Integer enthält.

procedure ShellSort(var f:array of integer);
var
  i, j, h, v, N: integer;
begin
  N := length(f);
  h := 1;
  repeat
    h := ( 3 * h ) + 1;
  until
    h < N;
  repeat
    h := ( h div 3 );
    for i := ( h + 1 ) to N do begin
      v := f[i];
      j := i;
      while ( ( j > h ) and ( f[j-h] > v ) ) do begin
        f[j] := f[j - h];
        dec( j, h );
      end;
      f[j] := v;
    end;
  until
    h = 1;
end;

Komplexität

Die Komplexität von Shellsort hängt von der Wahl der Folge für die Spaltenanzahl h ab. Mit der Folge 1, 3, 7, 15, 31, 63, ..., 2^k - 1 wird eine Komplexität von O(n^1,5) erreicht. Mit der Folge 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2^p3^q ist die Komplexität O(n·log(n)²). Eine Folge für O(n·log(n)) scheint jedoch nicht zu existieren. Es wurde experimentell belegt, dass die allgemeine Komplexität in O(n^1.25) liegt.

Variationen

Combsort arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit einem Durchlauf von Bubblesort sortiert, bevor die Spaltenanzahl verringert wird.

Literatur

• Donald L. Shell: A High-Speed Sorting Procedure. Commun. ACM 2(7): 30-32 (1959).