#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 5000000



/*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=50000;
 float zeit;
 clock_t start, ende;

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

 printf("\n\nSortieren von %d Elementen\n\n",elemente);
 printf("Sortieren von allen %d Elemente\n",elemente);
 /*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);
 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("Sortieren von keinem der %d Elemente\n",elemente);
 /*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);

 /*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);

 /*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*/  system("PAUSE");
 return 0;
}