Shellsort

aus Wikipedia, der freien Enzyklopädie

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

Inhaltsverzeichnis 1 Prinzip 2 Beispiel 3 Implementierung 3.1 Java 3.2 Pascal und Delphi 3.3 C 4 Komplexität 5 Variationen 6 Literatur

[Bearbeiten] 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.

Es sind viele Zahlenfolgen denkbar mit denen man sortieren könnte. Von Shell ursprünglich angedacht war "1,2,4,8,...,2n", was sich als ineffizient erwiesen hat. Heute populär ist die Folge "1,4,13,40,...,3*(Vorgänger)+1", da hier weniger Überlappungen entstehen.

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

[Bearbeiten] 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 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 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.

1 2 2 3 3 4 3 4 3 5 5 9  ->  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, ... 3n+1 erwiesen.

[Bearbeiten] Implementierung

[Bearbeiten] 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;
        }
    }
} 

[Bearbeiten] 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;

[Bearbeiten] C

Ein Array wird sortiert und vorher und nachher ausgegeben.

#include <stdio.h>

void tausche(int *ptr, int a, int b) 
{
  int tmp = ptr[a];
  ptr[a] = ptr[b];
  ptr[b] = tmp;   
}

void sort(int *ptr, int start, int end)
{
  int h;
  // erstes sort "shell"
  for(h=1; h<(end-start);h=3*h+1);     
  //erstelle sortier-sequenz rückwärts
  for (; h>0; h/=3)
  {
    //normales insertion sort
    int i;
    for (i=0; i<=end; i += h)
    {
      int j;
      for (j=i; j>=start; j -= h)
      {
        if ((j>0) && (ptr[j]<ptr[j-h]))
        {
          tausche(ptr,j,j-h);
        }
      }
    }
  }
}

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...\n");
  printf("Vorher: ");
  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;
}

[Bearbeiten] 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.

[Bearbeiten] Variationen

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

[Bearbeiten] 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