ein Kapitel zurück                                           ein Kapitel weiter

Shellsort ist eine Erweiterung zu Insertion Sort. Anstatt jedes benachbarte Element wie in Insertion Sort zu vergleichen und sortieren, vergleichen wir bei Shellsort jedes n-te Element (bei beliebigen Anfangselement). Damit ist es möglich Elemente miteinander zu sortieren, die in größeren Entfernungen voneinander liegen.

Dies machen wir mit einer beliebigen Folge von Werten mit n, bis n mit 1 beendet. Wenn n gleich von Anfang an 1 wäre können wir uns den Aufwand sparen, da die Insertion Sort entspräche.

Natürlich ist n abhängig von dessen Werten, man spricht dabei von Distanzen-Folgen. Je besser diese Folge, desto schneller werden die Daten sortiert. Die Suche nach der Optimalen Folge ist die Aufgabe des Programmierers. Hier nun der Quellcode zu Shellsort......

/*Download:shell.c*/

#include <stdio.h>

void shellsort(int array[], int elemente)
{
 int i,j,temp,n;

 n=elemente;
 for(; n>0; n/=3)    /*Distanz-Folge für n*/
   for(i=n+1; i<=elemente; i++)
     {
       temp=array[i];
       for(j=i; j>n && array[j-n]>temp; j-=n)
          array[j]=array[j-n];
       array[j]=temp;
     }
}


int main()
{
 int i;
 /*Unser Array zum sortieren*/
 int test_array[] = { 0, 5, 2, 7, 9, 1, 4, 3, 8, 6 };
 int N = sizeof(test_array)/sizeof(int);

 shellsort(test_array, N-1);

 for(i=0; i<N; i++)
   printf("%d ",test_array[i]);
 printf("\n");

 return 0;
}

Nun will ich ich Ihnen zeigen wie sie am besten herausfinden können, welches die optimale Distanz-Folge für Shellsort darstellt. Wer erstellen ein Array mit 2 Millionen Elementen, welches in umgekehrter Reihenfolge vorkommt. In diesem Fall müssen alle Elemente ausgetauscht werden, für die richtige Reihenfolge. Wir verwenden dabei eine Schleife und testen die Distanz-Folge von 2 bis 10.

Wir verwenden für unser Beispiel die Funktion clock(), welche für unsere Bedürfnisse vollkommend ausreicht (mehr zum Profiling entnehmen sie bitte aus Dementsprechenden Kapitel).

Hier nun unser Beispiel mit verschiedene Distanz-Folgen...

/*Download:shell_d.c*/

#include <stdio.h>
#include <time.h>
#define MAX 2000000
#define MAX_TEST 10


/*Unser Array zum sortieren*/
int test_array[MAX];

void init_test_array()
{
 int i,j;
 for(i=MAX,j=0; i>=0; i--,j++)
   test_array[j]=i;
}


void shellsort(int array[], int elemente, int distanz)
{
 int i,j,temp,n;

 n=elemente;
 for(; n>0; n/=distanz)
   for(i=n+1; i<=elemente; i++)
     {
       temp=array[i];
       for(j=i; j>n && array[j-n]>temp; j-=n)
          array[j]=array[j-n];
       array[j]=temp;
     }
}


int main()
{
 int i;
 int distanz_folge;
 float zeit;
 clock_t start, ende;

 for(distanz_folge=2; distanz_folge <= MAX_TEST; distanz_folge++)
  {
    init_test_array();
    start = clock();
    shellsort(test_array, MAX-1, distanz_folge);
    ende = clock();
    /*Ergebniss der Laufzeitmessung in Sekunden*/
    zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
    printf("Die Laufzeitmessung mit der Distanz-Folge %d ergab %.2f  Sekunden\n"
            ,distanz_folge,zeit);
  }

 return 0;
}

Je nach Power des Rechners kommt nun folgende Ausgabe (500 MHZ Celron, 160MB RAM)... 

Die Laufzeitmessung mit der Distanz-Folge 2 ergab 7.10 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 3 ergab 5.81 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 4 ergab 5.45 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 5 ergab 5.47 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 6 ergab 5.67 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 7 ergab 5.95 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 8 ergab 5.78 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 9 ergab 6.47 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 10 ergab 7.03 Sekunden

In diesem Fall scheint eine Distanz-Folge zwischen 4 und 6 das optimalste Ergebnis zu zeigen. Diese Tests von Laufzeitmessungen mit Shellsort werden sie wohl immer durchführen müssen, da bisher noch niemand in der Lage war, Shellsort zu analysieren. Aber im Vergleich zu Insertions Sort läuft Shellsort immer schneller ab. Sie können ja mal Insertions Sort zum Vergleich Miteinbauen....

/*Download:sh_ins.c*/

#include <stdio.h>
#include <time.h>
#define MAX 10000
#define MAX_TEST 10


/*Unser Array zum sortieren*/
int test_array[MAX];

void init_test_array()
{
 int i,j;
 for(i=MAX,j=0; i>=0; i--,j++)
   test_array[j]=i;
}


void shellsort(int array[], int elemente, int distanz)
{
 int i,j,temp,n;

 n=elemente;
 for(; n>0; n/=distanz)
   for(i=n+1; i<=elemente; i++)
     {
       temp=array[i];
       for(j=i; j>n && array[j-n]>temp; j-=n)
          array[j]=array[j-n];
       array[j]=temp;
     }
}

void insertion(int array[], int elemente)
{
 int i,j,temp;

 for(i=1; i<=elemente; i++)
  {
   temp=array[i]; /*aktuelles Element zwischenspeichern*/
   for(j=i; array[j-1] > temp && j > 0; j--)
     array[j] = array[j-1]; /*Wenn Vorgänger größer als aktuelles Element in temp*/
   array[j]=temp; /*gespeichertes Element an neue Position*/
  }
}



int main()
{
 int i;
 int distanz_folge;
 float zeit;
 clock_t start, ende;

 for(distanz_folge=2; distanz_folge <= MAX_TEST; distanz_folge++)
  {
    init_test_array();
    start = clock();
    shellsort(test_array, MAX-1, distanz_folge);
    ende = clock();
    /*Ergebniss der Laufzeitmessung in Sekunden*/
    zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
    printf("Die Laufzeitmessung mit der Distanz-Folge %d ergab %.2f Sekunden\n"
            ,distanz_folge,zeit);
  }

  /*Insertions Sort Laufzeittest*/
    init_test_array();
    start = clock();
    insertion(test_array, MAX-1);
    ende = clock();
    /*Ergebniss der Laufzeitmessung in Sekunden*/
    zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
    printf("Die Laufzeitmessung mit Insertions Sort ergab %.2f Sekunden\n",zeit);


 return 0;
}

Ich habe die Anzahl der Elemente im Array auf 10000 reduziert, da sonst mit Insertions Sort kein Vernünftiges Arbeiten mehr möglich zu sein scheint. Hier meine Ausgabe des Programms........... 

Die Laufzeitmessung mit der Distanz-Folge 2 ergab 0.02 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 3 ergab 0.01 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 4 ergab 0.02 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 5 ergab 0.01 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 6 ergab 0.01 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 7 ergab 0.02 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 8 ergab 0.01 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 9 ergab 0.02 Sekunden
Die Laufzeitmessung mit der Distanz-Folge 10 ergab 0.02 Sekunden
Die Laufzeitmessung mit Insertionssort ergab 3.39 Sekunden

Ich denke mal das Ergebnis spricht für sich.

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf