Algorithmen und Datenstrukturen in C/ Shellsort

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.

Es sind viele Zahlenfolgen denkbar mit denen man sortieren könnte. Von Shell ursprünglich gedacht 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. (Siehe <1> im Code.)

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 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 die Folge 1, 4, 13, … (Berechnungsvorschrift: Wert_n = 3 ⋅ (Wert_n - 1) + 1) erwiesen.

Am Ende wird mit h=1 das ganze Verfahren wiederholt, was zur Sicherheit des Verfahrens führt.

Implementierung

#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
   {
      /* <1>
       * Hier wird die Neue Spaltenzahl ermittelt. Dabei kommt es auf       folgende Dinge an:
       */
      /* step/=2; */       /* unsprüngliche Methode, veraltet weil langsamm */
      step=(step-1)/3;     /* Neue Methode, hier wird sie Zahl der Spalten deutlich schneller reduziert. */

      for(int start=0;start<step;++start)
      {
         for(int i=start+1;i<size;i+=step)
         {
            /* Hier werden die Matritzen ineinander "geschoben".
             * Prinzipiell besteht die Möglichkeit Ein anderes Verfahren zu verwenden.
             */
            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;
}

Die Implementierung an sich ist trivial, sollte aber trotzdem genauer erläutert werden.

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 a*b-sortierte Folge auch a-sortiert und b-sortiert ist, sodass es dann zu unnützen Sortierschritt käme.

Variationen

Die "Einsortierung" wird bei der oben genannten Implementierung durch Insertionsort erledigt. Diese Verfahren kann man durch Bubblesort ersetzen, wodurch man den Combsort erhält.

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

Belege

<< Selectionsort | Inhaltsverzeichnis | Mergesort >>