„Shellsort“ – Versionsunterschied

Shellsort ist ein von Donald L. Shell im Jahre 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert.

Prinzip

Shellsort bedient sich prinzipiell Insertionsort. Es versucht den Nachteil auszugleichen, dass hier Elemente in der Sequenz oft über weite Strecken verschoben werden müssen. Dies macht Insertionsort ineffizient. Shellsort verfolgt den Ansatz, dass die Sequenz z.B. erst 4-sortiert wird, dann 2-sortiert, und zuletzt mit normalem Insertionsort sozusagen 1-sortiert.

Anschaulich wäre dies anhand von Hilfsmatrizen darzustellen (siehe Beispiel):

• Die Daten werden in eine k-spaltige Matrix geschrieben
• Die Spalten der Matrix werden einzeln sortiert

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

Shellsort arbeitet in-place, gehört jedoch nicht zu den stabilen Sortieralgorithmen.

Beispiel

Zu sortieren sind die Zahlen "2 5 3 4 3 9 3 2 5 4 1 3" mittels der Folge 2n,...,4,2,1.

Zuerst werden die Daten in eine Matrix mit 4 Spalten eingetragen und spaltenweise sortiert. Die Zahlenfolge wird also 4-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 2-sortiert.

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

Die sortierte 2-Spalten-Matrix wird nun in eine Spalte geschrieben und wieder sortiert mittels normalem Insertionsort. Der Vorteil dabei besteht darin, dass kein Element der Sequenz so weit verschoben werden muss, wie bei Insertionsort, das auf eine völlig unsortierte Folge losgelassen wird.

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

Die hier verwendete Folge 1,2,4,8,16,...,2n (wie es 1959 original von Shell vorgeschlagen wurde) erweist sich in der Praxis allerdings als nicht zweckmäßig, da nur gerade Stellen sortiert werden und ungerade Stellen der Sequenz nur im letzten Schritt angefasst werden. Als zweckmäßiger hat sich 1,4,13, ... 3(n-1)+1 erwiesen.

Implementierung

Java 5

Shell sort ist eine Verbesserung des Algorithmus straight insertion. Dort wandern nämlich die Elemente in Einzelschritten auf ihren Platz: Nach dem Finden des kleinsten Elements werden die dazwischenliegenden einzeln hochgeschoben und nur das kleinste „springt“. Die meisten (d.h. n) Elemente werden von ihrem ursprünglichen Platz in durchschnittlich n/3 Schritten zu ihrem endgültigen Platz geschoben.

Beim Shell-Sort führt man abnehmende Schrittweiten k[1], k[2], … k[t] ein, wobei die letzte Schrittweite immer k[t] = 1 ist. Es werden nacheinander t Schritte durchgeführt; im m-ten Schritt springen die Elemente in Richtung ihres zukünftigen Platzes um jeweils k[m] Stellen. Im ersten Schritt werden diejenigen Elemente untereinander sortiert, die k[1] Stellen voneinander entfernt sind; dann diejenigen, die eine Entfernung k[2] voneinander haben usw. Das Effekt dieser Vorgehensweise ist es, dass die Elemente im ersten Durchgang nicht um einen, sondern um k[1] Stellen zu ihrem Platz „springen“.

Die letzte Schrittweite k[t] ist 1, d.h. zum Schluss wird ein ganz normaler Sortiervorgang straight insertion durchgeführt. Dies garantiert, dass am Ende die Reihung sortiert ist. Der Algorithmus braucht jedoch kaum noch etwas zu tun, da die vorherigen Schritte die Reihung schon fast vollständig sortiert haben.

Durch die geeignete Wahl der Schrittweiten k[1], k[2], … k[t] kann der Sortieraufwand deutlich reduziert werden. Für die Schrittweiten (1, 3, 7, 15, 31, … ) wurde nachgewiesen (s. Donald E. Knuth: The Art of Computer Programming), dass die Zeitkomplexität des Algorithmus n hoch 1,2 beträgt, das deutlich besser ist, als die quadratische Komplexität von [bubble sort], [insertion sort] oder [selection sort], jedoch schlechter als die Komplexität n log n von [Quicksort] oder [Heapsort].

/** Autor: Andreas Solymosi, 2007
    Quelle: Solymosi/Grude: Grundkurs Algorithmen und Datenstrukturen, Vieweg Verlag, ISBN 3-528-05743-2 */
static <E extends Comparable<E>> void shellSort(E[] sammlung, final int[] schrittweiten) {
  for (int schrittweite : schrittweiten) { // straight insertion mit schrittweite
     for (int index = schrittweite; index < sammlung.length; index++){
        E elementZumEinfuegen = sammlung[index];
        int einfuegestelle = index;
        while (einfuegestelle - schrittweite >= 0 &&  
              elementZumEinfuegen.compareTo(sammlung[einfuegestelle-schrittweite]) < 0) {
           sammlung[einfuegestelle] = sammlung[einfuegestelle - schrittweite];
           einfuegestelle -= schrittweite; // Sprung um schrittweite
        }
        sammlung[einfuegestelle] = elementZumEinfuegen;
     }
  }
}

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 Spalte. Die Spalten werden per Insertionsort sortiert, da dieser Algorithmus von einer Vorsortierung der Daten profitieren kann.

In folgendem Programm werden die Daten zuerst in h=2147483647 Spalten angeordnet, sofern so viele Daten vorhanden sind. Wenn nicht, wird die for-i-Schleife übersprungen und mit h=1131376761 fortgefahren usw.

void shellsort (int[] a, int n)
{   
    int i, j, k, h, t;

    int[] spalten = {2147483647, 1131376761, 410151271, 157840433,
    58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331,
    84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1};

    for (k=0; k<23; k++)
    {   
        h=spalten[k];
        // Sortiere die "Spalten" mit Insertionsort
        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;

C

Ein Array wird sortiert und vorher und nachher ausgegeben.

#include <stdio.h>

inline void tausche(int *a, int *b) {
   (unsigned) *a ^= (unsigned) *b;
   (unsigned) *b ^= (unsigned) *a;
   (unsigned) *a ^= (unsigned) *b;
}

void sort(int *array,int size, ) {
   int step=size;
   do
   {
      step/=2;
      for(int start=0;start<step;++start)
      {
         for(int i=start+1;i<size;i+=step)
         {
            for(int j=i-1;j>=0;j-=step)
               if(array[j]>array[j+step])
                  tausche(&array[j],&array[j+step]);
               else
                  break;
         };
      };
   }while(step>0);
}

int main()  {
  int n = 0;
  int x[30] = {30,5,24,11,26,20,4,23,9,25,6,28,15,27,7,22,10,3,1,13,21,29,17,2,19,8,16,14,12,18};
  printf("Shellsort...\nVorher: ");
  for (n = 0;n < 30;n++) printf("%d|",x[n]);
  sort(x, 0, 29);
  printf("\n\nNachher:");
  for (n = 0;n < 30;n++) printf("%d|",x[n]);
  
  return 0;
}

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)²). Es wurde experimentell belegt, dass die allgemeine Komplexität höchstwahrscheinlich in O(n^1.25) liegt. Eine Folge für O(n·log(n)) scheint jedoch nicht zu existieren.

Die Suche nach einer optimalen Folge, gestaltet sich dabei als äußerst schwierig. Zu große Abstände zwischen den Folgegliedern ergeben zu große Verschiebungen, zu enge Abstände bewirken zu viele Durchläufe bis zur letztendlichen Sortierung. Dabei gilt es bei der Wahl einer Folge zu vermeiden, dass sie gemeinsame Teiler haben, da eine Folge a*b-sortierte Folge auch a-sortiert und b-sortiert ist, sodass es dann zu unnützen Sortierschritt käme.

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).
• Robert Sedgewick: Algorithms in Java, Part 1-4 Addison-Wesley, ISBN 0201361205

Weblinks

Wikibooks: Algorithmen und Datenstrukturen in C: Shellsort – Lern- und Lehrmaterialien

• Shellsort Java Applet