ein Kapitel zurück                                           ein Kapitel weiter

Nun wollen wir unser Sortieralgorithmen ein wenig analysieren. Wir werden ein Programm schreiben welches 3 verschieden Zustände von Daten sortieren soll.

  • Zuerst sollen Daten sortiert werden, bei dem das größte Element ganz am Anfang ist und absteigend das kleinste Element ganz am Ende. Dies stellt auch Gleichzeitig die schlechteste Vorraussetzung für Sortieralgorithmen da, weil alle Elemente bewegt werden müssen.
  • Anschließend sollen Daten sortiert werden, welche schon in Sortierter Form vorliegen. Denn es kann ja immer mal vorkommen das Herr Meier die Daten sortiert hat und Herr Müller weis wieder mal nichts davon und sortiert diese nochmals.
  • Als letztes Beispiel wollen wir Daten sortieren welchen mit Zufallsdaten belegt werden.

Die Anzahl der Elemente ist in eine solchem Fall natürlich auch entscheidend. Wir verwenden 500, 5000 und am Schluss 50000 Elemente die nach den eben genannten Zuständen sortiert werden sollen.

Wegen der schlecht laufenden Performance im schlechtesten Fall habe ich Quicksort im ersten Fall auskommentiert. Wollen sie dies dennoch testen empfehle ich Ihnen das Programm über Nacht laufen zu lassen ;)
Auch im dritte Fall, dem Sortieren von Zufallszahlen habe ich Quicksort auskommentiert. Ich überlasse es Ihnen ob sie diesen Algorithmus dennoch mittesten wollen.

Ich habe das Programm der Übersicht wegen etwas zusammengepresst. Uns soll nur die Ausgabe des Programms interessieren. Leiten sie die Standardausgabe am besten in eine Textdatei um.

Hier nun unser kleines Benchmark einiger Sortieralgorithmen.....

/*Download:bench.c*/

#include <stdio.h>
#include <time.h>
/*#define MAX 50000*/



/*Ein Array von großen zu kleinen Werten*/
int test_array[MAX];

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

/*Ein bereits sortiertes Array*/
void init_test_array2(int elements)
{
 int i;
 for(i=0; i<=elements; i++){
   test_array[i]=i;
   }
}

/*Ein Array mit (Pseudo)-Zufallszahlen*/
void init_test_array3(int elements)
{
 int i,j;
 for(i=0; i<=elements; i++)
   test_array[i]=rand();
}



void merge(int [], int, int);

void mergesort(int array[], int low, int high)
{
 int m;
 if(low<high)
  {
    m=(low+high)/2;
    mergesort(array, low, m);
    mergesort(array, m+1, high);
    merge(array, low, high);
  }
}

void merge(int array[], int low, int high)
{
 int i,j,k=0,m, n=high-low+1;
 int b[high-low+1];

 m=(low+high)/2;
 /*linke Hälte in Array b kopieren*/
 for(i=low; i<=m; i++)
   b[k++] = array[i];
 /*rechte Hälfte in umgekehrter Reihenfolge in Array b kopieren*/
 for(j=high; j>=m+1; j--)
   b[k++] = array[j];

 i=0; j=n-1; k=low;

 /*Nun das Nächstgrößere Element zurückkopieren bis i und j sich überkreuzen*/
 while(i<=j)
    (b[i]<=b[j])?(array[k++]=b[i++]):(array[k++]=b[j--]);
}



void quicksort(int array[], int links, int rechts)
{
 int v,i,j,temp;

 if(rechts > links)
  {
   v=array[rechts];
   i=links-1;
  j =rechts;
  for(;;)
   {
     while(array[++i] < v);
     while(array[--j] > v);
     if(i >= j)
       break;
     temp=array[i];
     array[i]=array[j];
     array[j]=temp;
   }
  temp=array[i];
  array[i]=array[rechts];
  array[rechts]=temp;
  quicksort(array, 1, i-1);
  quicksort(array, i+1, rechts);
  }
}

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;
     }
}

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

 for(i=0; i<elemente; i++)
  {
    mini=i;
    for(j=i+1; j<=elemente; j++)
     {
      if(array[j] < array[mini])
        mini=j;
     }
    temp=array[mini];
    array[mini]=array[i];
    array[i]=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*/
  }
}


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

 while(elemente--)
   for(i = 1; i <= elemente; i++)
     if(array[i-1]>array[i])
      {
        temp=array[i];
        array[i]=array[i-1];
        array[i-1]=temp;
      }
}



int main()
{
 int i;
 int elemente=500;
 float zeit;
 clock_t start, ende;

 for(i=1; i<=3; i++, elemente*=10){

 printf("\n\nSortieren von %d Elementen\n\n",elemente);
 /*printf("Bitte ENTER druecken\n"); getchar();*/
 printf("\n%d. Versuch : alle %d Elemente muessen sortiert werden\n\n",i,elemente);
 /*Selectionsort*/
 init_test_array(elemente);  start = clock(); selection(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Selectionsort: %.2f Sekunden\n",zeit);
 /*Insertionsort*/
 init_test_array(elemente);  start = clock(); insertion(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Insertionsort: %.2f Sekunden\n",zeit);
 /*Bubblesort*/
 init_test_array(elemente);  start = clock(); bubble(test_array, elemente);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Bubblesort   : %.2f Sekunden\n",zeit);
 /*Shellsort*/
 init_test_array(elemente);  start = clock(); shellsort(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Shellsort    : %.2f Sekunden\n",zeit);
 /*Quicksort*/
/* init_test_array(elemente);  start = clock(); quicksort(test_array, 1, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Quicksort    : %.2f Sekunden\n",zeit);  */
 /*Mergesort*/
 init_test_array(elemente);  start = clock(); mergesort(test_array, 0, elemente);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Mergesort    : %.2f Sekunden\n",zeit);

 /*2. Versuch eine bereits Sortierte Liste*/
 printf("\n%d. Versuch : keins der %d Elemente muss sortiert werden\n\n",i,elemente);
 /*Selectionsort*/
 init_test_array2(elemente);  start = clock(); selection(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Selectionsort: %.2f Sekunden\n",zeit);
 /*Insertionsort*/
 init_test_array2(elemente);  start = clock(); insertion(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Insertionsort: %.2f Sekunden\n",zeit);
 /*Bubblesort*/
 init_test_array2(elemente);  start = clock(); bubble(test_array, elemente);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Bubblesort   : %.2f Sekunden\n",zeit);
 /*Shellsort*/
 init_test_array2(elemente);  start = clock(); shellsort(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Shellsort    : %.2f Sekunden\n",zeit);
 /*Quicksort*/
 init_test_array2(elemente);  start = clock(); quicksort(test_array, 1, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Quicksort    : %.2f Sekunden\n",zeit);
 /*Mergesort*/
 init_test_array(elemente);  start = clock(); mergesort(test_array, 0, elemente);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Mergesort    : %.2f Sekunden\n",zeit);

 /*3.Versuch Zufallsdaten*/
 printf("\n%d. Versuch : Zufallszahlen muessen sortiert werden\n\n",i,elemente);
 /*Selectionsort*/
 init_test_array3(elemente);  start = clock(); selection(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Selectionsort: %.2f Sekunden\n",zeit);
 /*Insertionsort*/
 init_test_array3(elemente);  start = clock(); insertion(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Insertionsort: %.2f Sekunden\n",zeit);
 /*Bubblesort*/
 init_test_array3(elemente);  start = clock(); bubble(test_array, elemente);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Bubblesort   : %.2f Sekunden\n",zeit);
 /*Shellsort*/
 init_test_array3(elemente);  start = clock(); shellsort(test_array, elemente-1);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Shellsort    : %.2f Sekunden\n",zeit);
 /*Quicksort*/
 /*init_test_array3(elemente);  start = clock(); quicksort(test_array, 1, elemente-1);
  ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
  printf("Quicksort    : %.2f Sekunden\n",zeit);  */
 /*Mergesort*/
 init_test_array3(elemente);  start = clock(); mergesort(test_array, 0, elemente);
 ende = clock();  zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
 printf("Mergesort    : %.2f Sekunden\n",zeit);
 }/*Ende for*/
 return 0;
}

Nun wollen wir unser Ausgabe analysieren, die je nach Geschwindigkeit des Rechners unterschiedlich sein wird.

Zuerst als das Sortieren von 500 Elementen....... 

Sortieren von 500 Elementen


1. Versuch : alle 500 Elemente muessen sortiert werden

Selectionsort: 0.00 Sekunden
Insertionsort: 0.00 Sekunden
Bubblesort   : 0.05 Sekunden
Shellsort    : 0.00 Sekunden
Mergesort    : 0.00 Sekunden

1. Versuch : keins der 500 Elemente muss sortiert werden

Selectionsort: 0.00 Sekunden
Insertionsort: 0.00 Sekunden
Bubblesort   : 0.00 Sekunden
Shellsort    : 0.00 Sekunden
Quicksort    : 0.00 Sekunden
Mergesort    : 0.00 Sekunden

1. Versuch : Zufallszahlen muessen sortiert werden

Selectionsort: 0.00 Sekunden
Insertionsort: 0.00 Sekunden
Bubblesort   : 0.06 Sekunden
Shellsort    : 0.00 Sekunden
Mergesort    : 0.00 Sekunden

Daran können sie erkennen, das sie sich bei der Auswahl des Sortieralgorithmus von kleinen Daten keine allzu große Gedanken machen brauchen. Für 500 Elementen braucht kein Algorithmus hier nennenswerte Laufzeiten. Hierbei können sie also den für Sie am einfachsten zu Implemierenden Algorithmus verwenden.

Sehen wir uns an wie es bei 5000 Elementen aussieht..... 

Sortieren von 5000 Elementen


2. Versuch : alle 5000 Elemente muessen sortiert werden

Selectionsort: 0.84 Sekunden
Insertionsort: 0.82 Sekunden
Bubblesort   : 1.76 Sekunden
Shellsort    : 0.00 Sekunden
Mergesort    : 0.06 Sekunden

2. Versuch : keins der 5000 Elemente muss sortiert werden

Selectionsort: 0.60 Sekunden
Insertionsort: 0.00 Sekunden
Bubblesort   : 0.71 Sekunden
Shellsort    : 0.00 Sekunden
Quicksort    : 0.39 Sekunden
Mergesort    : 0.05 Sekunden

2. Versuch : Zufallszahlen muessen sortiert werden

Selectionsort: 0.66 Sekunden
Insertionsort: 0.50 Sekunden
Bubblesort   : 1.32 Sekunden
Shellsort    : 0.05 Sekunden
Mergesort    : 0.00 Sekunden

In diesem Beispiel zeigt sich schon mal das Bubblesort immer das schlechteste Laufzeitverhalten aufweist.
Selectionsort hingegen zeigt bei allen 3 Zuständen eine ziemliche konstante Leistung.
Insertionsort sticht bei einem bereits Sortierten Zustand besonders hervor und ist in allen 3 Fällen besser als Selectionsort.
Shellsort und Mergesort verbrauchen bei 5000 Elementen immer noch kaum nennenswerte Zeit.

Bei der nächsten Analyse mit 50000 Elementen dürften wir ein noch etwas eindeutigeres Ergebnis bekommen....... 

Sortieren von 50000 Elementen


3. Versuch : alle 50000 Elemente muessen sortiert werden

Selectionsort: 84.86 Sekunden
Insertionsort: 117.38 Sekunden
Bubblesort   : 194.43 Sekunden
Shellsort    : 0.11 Sekunden
Mergesort    : 0.39 Sekunden

3. Versuch : keins der 50000 Elemente muss sortiert werden

Selectionsort: 83.10 Sekunden
Insertionsort: 0.00 Sekunden
Bubblesort   : 86.67 Sekunden
Shellsort    : 0.06 Sekunden
Quicksort    : 61.02 Sekunden
Mergesort    : 0.44 Sekunden

3. Versuch : Zufallszahlen muessen sortiert werden

Selectionsort: 85.08 Sekunden
Insertionsort: 59.05 Sekunden
Bubblesort   : 185.59 Sekunden
Shellsort    : 0.17 Sekunden
Mergesort    : 0.33 Sekunden

Hier verfestigen wir nochmals die Aussage von Selectionsort von zuvor. Selectionsort benötigt immer die selbe Zeit. Daher kann man bei Selectionsort von einem stabilen Sortieralgorithmus sprechen. Die Zeit von Selectionsort bei 50000 Elementen hingegen macht nicht mehr einen so glänzenden Eindruck.

Wenn sie nun wählen müssten zwischen Insertionssort und Selectionssort, müssen sie abschätzen in welchem Zustand sich Ihre Daten vor dem Sortieren immer befinden. Im absoluten schlechtesten Fall sind sie mit Selectionsort besser beraten. So gut wie sortierte Daten meistert Insertionssort besser und allgemein am besten von allen.
Bubblesort fällt hier entgültig aus dem Rennen und eignet sich überhaupt nicht mehr zum sortieren einer größeren Datenmenge.
Shellsort und Mergesort sind mit den 50000 Elementen nicht sonderlich beschäftigt. Daher habe ich die beiden nochmals mit einem extra großen Happen beauftragt.... 

4. Versuch : alle 5000000 Elemente muessen sortiert werden

Shellsort    : 16.70 Sekunden
Mergesort    : 44.53 Sekunden

4. Versuch : keins der 5000000 Elemente muss sortiert werden

Quicksort    : 13.07 Sekunden
Mergesort    : 49.92 Sekunden

4. Versuch : 5000000 Zufallszahlen muessen sortiert werden

Shellsort    : 54.16 Sekunden
Mergesort    : 49.48 Sekunden

In den ersten beiden Fällen war Shellsort eindeutig die besten Möglichkeit 5 Millionen Elemente zu sortieren. Aber im letzten Beispiel zeigt sich, das hier keine Eindeutige Empfehlung gemacht werden kann. Sollten sie zwischen diesen beiden Algorithmen wählen müssen, so müssen sie dies selbst testen an Ihrem Programm.

Ich hoffen Ihnen damit einen kleinen Überblick zu den Sortieralgorithmus verschafft zu haben. Anhand dieses Kaptitels konnten sie schon sehen, daß ein Algorithmus immer getestet werden muss. In den wenigsten Fällen kann man sagen, welcher der Beste ist (abgesehen von wenigen Elementen die Sortiert werden müssen). Sie haben aber auch gesehen, daß es sich lohnt Algorithmen zu testen.

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf