#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MIN 30
int *b;

void versickern(int a[], int n, int i){
  int j, h=a[i];
  if(i<0) return;
  while(i<n/2){
    j=i+i+1;
    if(j+1<n && a[j]<a[j+1]) j++;
    if(h>=a[j]) break;
    a[i]=a[j]; i=j;
  }
  a[i]=h;
}

void konstruktion(int a[], int n){
  int i;
  for(i=n/2-1; i>=0; i--)
    versickern(a,n,i);
}

void heapsort(int a[], int n){
  int i, tmp;
  konstruktion(a,n);
  for(i=n-1; i>=0; i--){
    tmp=a[0]; a[0]=a[i]; a[i]=tmp;
    versickern(a,i,0);
  }
}


void mergesort(int a[], int l, int r){          //l=linker Rand, r=rechter Rand
    if(r>l){
        int i, j, k, m;                         //Variablen deklarieren
        m=(r+l)/2;                              //Mitte ermitteln
        mergesort(a, l, m);                     //linke Teildatei
        mergesort(a, m+1, r);                   //rechte Teildatei
        for(i=m+1; i>l; i--) b[i-1]=a[i-1];     //linke  Teildatei in Hilfsarray
        for(j=m; j<r; j++) b[r+m-j]=a[j+1];     //rechte Teildatei umgedreht in Hilfsarray
        for(k=l; k<=r; k++)
            a[k]=(b[i]<b[j])?b[i++]:b[j--];     //füge sortiert in a ein
    }
}


void mergesort_it(int a[], int n){              //n=Elementezahl
    int step, i, j, k, m, l, r;
    for(step=2; step<n*2; step*=2){             //verdopple sequentiell die Dateilänge
        r=-1;                                   //Anfangswert für rechte Grenze
        while(r<n){                             //solange Folge nicht komplett betrachet
            l=r+1;                              //linken Rand auf bisher rechte Grenze+1
            r+=step;                            //rechten Rand um step erhöhen
            m=(l+r)/2;                          //Mitte finden
            if(r>n){                            //wenn über das Ziel hinaus geschossen
                r=n;                            //dann auf letztes Element setzen
                if(m>r) m=(l+r)/2;              //wenn Mitte hinter r liegt, neu berechnen
            }
            for(i=m+1; i>l; i--) b[i-1]=a[i-1]; //linke  Teildatei in Hilfsarray
            for(j=m; j<r; j++) b[r+m-j]=a[j+1]; //rechte Teildatei umgedreht in Hilfsarray
            for(k=l; k<=r; k++)
                a[k]=(b[i]<b[j])?b[i++]:b[j--]; //füge sortiert in a ein
        }
    }
}


void quicksort(int a[], int l, int r){          //a=Array, l=linker Rand, r=rechter Rand
    if(r>l){                                    //solange mehr als 1 Folgenelement existiert
        int i=l-1, j=r, tmp;                    //Variableninitialisierung mit Folgenrändern
        for(;;){                                //Endlosschleife; bricht ab, wenn i>=j
            while(a[++i]<a[r]);                 //inkrem., bis größeres  Element gefunden wird
            while(a[--j]>a[r] && j>i);          //dekrem., bis kleineres Element gefunden wird
	    if(i>=j) break;                     //brich ab, wenn sich die Folgenzeiger treffen
            tmp=a[i]; a[i]=a[j]; a[j]=tmp;      //tausche kleineres mit größerem Element
        }
        tmp=a[i]; a[i]=a[r]; a[r]=tmp;          //tausche Trennelement

        quicksort(a, l, i-1);                   //rekursiver Aufruf für linke Teilfolge
        quicksort(a, i+1, r);                   //rekursiver Aufruf für rechte Teilfolge
    }
}


  void qsort_comb(int a[], int l, int r){
        int i, j, tmp;
        if(r-l > MIN){ //Quicksort
          i=l-1; j=r;
          if(r-l > 3){ //Median of three
                int m=l+(r-l)/2;
                if(a[l]>a[m])
                  { tmp=a[l]; a[l]=a[m]; a[m]=tmp; }
                if(a[l]>a[r])
                  { tmp=a[l]; a[l]=a[r]; a[r]=tmp; }
                else if(a[r]>a[m])
                  { tmp=a[r]; a[r]=a[m]; a[m]=tmp; }
          }

          for(;;){
                while(a[++i]<a[r]);
                while(a[--j]>a[r] && j>i);
                if(i>=j) break;
                tmp=a[i]; a[i]=a[j]; a[j]=tmp;
          }
          tmp=a[i]; a[i]=a[r]; a[r]=tmp;

          qsort_comb(a, l, i-1);
          qsort_comb(a, i+1, r);
        }
        else{ //insertion sort
          for(i=l+1; i<=r; ++i){
                tmp=a[i];
                for(j=i-1; j>=l && tmp<a[j]; --j)
                  a[j+1]=a[j];
                a[j+1]=tmp;
          }
        }
  }

  
inline unsigned getbit(unsigned x, int k){ return (x>>k)&1; }

void radixexchange(int a[], int l, int r, int b){
    b--;
    int t, i, j;
    if(r>l && b>=0){
        i=l; j=r;
        while(j!=i){
            while(getbit(a[i],b)==0 && i<j) i++;
            while(getbit(a[j],b)!=0 && j>i) j--;
            t=a[i]; a[i]=a[j]; a[j]=t;
        }
        if(getbit(a[r],b)==0) j++;
        radixexchange(a,l,j-1,b);
        radixexchange(a,j,r,b);
    }
}


void straightradix(int a[], int N, int bits){
    int i, pass, count[2], b[N];
    for(pass=0; pass<bits; pass++){                     //die Bits der Reihe nach betrachten
        count[0]=0; count[1]=0;                         //count[] mit 0 initialisieren
        for(i=0; i<N; i++) count[getbit(a[i],pass)]++;  //Vorkommen der Bits speichern
        count[1]=count[0]+count[1];                     //Position im Array bestimmen
        for(i=N-1; i>=0; i--)
            b[--count[getbit(a[i],pass)]]=a[i];         //in b einordnen, jeweiligen Zähler verringern
        for(i=0; i<N; i++) a[i]=b[i];                   //auf a zurück speichern
    }
}


inline unsigned getbits(unsigned x, int k, int j){ return (x>>k)&~(~0<<j); }

void linstraightradix(int a[], int N, int bits, int m){
    int M=1, i, j, pass, *count, b[N];
    for(i=0; i<m; i++,M*=2);				//m^2 berechnen
    if(m<=0 || m>bits/2) m=bits/4;                      //ungültige Fälle auf guten Fall abbilden
    count=(int*)malloc(M*sizeof(int));
    for(pass=0; pass<bits/m; pass++){                   //die Bits der Reihe nach betrachten
        for(j=0; j<M; j++) count[j]=0;                  //count[] mit 0 initialisieren
        for(i=0; i<N; i++) count[getbits(a[i],pass*m,m)]++;     //Vorkommen der Schlüssel speichern
        for(j=1; j<M; j++)
            count[j]=count[j-1]+count[j];                       //Positionen im Array bestimmen
        for(i=N-1; i>=0; i--)
            b[--count[getbits(a[i],pass*m,m)]]=a[i];            //in b einordnen, jeweiligen Zähler verringern
        for(i=0; i<N; i++) a[i]=b[i];                   //auf a zurück speichern
    }
    free(count);
}


int main(void){
	int i, n;
	int *a, *c;
	clock_t start, ende;
	srand(time(0));
	
	printf("Wieviele Elemente?: ");
	scanf("%d",&n);
	
	a=(int*)malloc(n*sizeof(int));
	c=(int*)malloc(n*sizeof(int));
	b=(int*)malloc(n*sizeof(int));
		
	for(i=0; i<n; i++){
		a[i]=rand()%(n/2)+1;
		c[i]=a[i];
	}
	
	/*for(i=0; i<n; i++)
		printf("%d, ",a[i]);
	printf("\b\b  \n\n");
	*/
	start=clock();
	mergesort(a,0,n-1);
	ende=clock();
	printf("Rekursives Mergesort:\t %6.3f\n",(ende-start)/(float)CLOCKS_PER_SEC);
	for(i=0; i<n; i++){
		//printf("%d, ",a[i]);
		a[i]=c[i];
	}
	//printf("\b\b  \n");
		
	start=clock();
	mergesort_it(a,n-1);
	ende=clock();
	printf("Iteratives Mergesort:\t %6.3f\n",(ende-start)/(float)CLOCKS_PER_SEC);
	for(i=0; i<n; i++){
		//printf("%d, ",a[i]);
		a[i]=c[i];
	}
	//printf("\b\b  \n");
	
	start=clock();
	heapsort(a,n);
	ende=clock();
	printf("Reines Heapsort:\t %6.3f\n",(ende-start)/(float)CLOCKS_PER_SEC);
	for(i=0; i<n; i++){
		//printf("%d, ",a[i]);
		a[i]=c[i];
	}
	//printf("\b\b  \n");
	
	start=clock();
	quicksort(a,0,n-1);
	ende=clock();
	printf("Reines Quicksort:\t %6.3f\n",(ende-start)/(float)CLOCKS_PER_SEC);
	for(i=0; i<n; i++){
		//printf("%d, ",a[i]);
		a[i]=c[i];
	}
	//printf("\b\b  \n");
	
	start=clock();
	qsort_comb(a,0,n-1);
	ende=clock();
	printf("Verbessertes Quicksort:\t %6.3f\n",(ende-start)/(float)CLOCKS_PER_SEC);
	for(i=0; i<n; i++){
		//printf("%d, ",a[i]);
		a[i]=c[i];
	}
	//printf("\b\b  \n");
	
	start=clock();
	radixexchange(a,0,n-1,32);
	ende=clock();
	printf("Radix Exchange Sort:\t %6.3f\n",(ende-start)/(float)CLOCKS_PER_SEC);
	for(i=0; i<n; i++){
		//printf("%d, ",a[i]);
		a[i]=c[i];
	}
	//printf("\b\b  \n");
	
	start=clock();
	straightradix(a,n,32);
	ende=clock();
	printf("Straight Radix Sort:\t %6.3f\n",(ende-start)/(float)CLOCKS_PER_SEC);
	for(i=0; i<n; i++){
		//printf("%d, ",a[i]);
		a[i]=c[i];
	}
	//printf("\b\b  \n");
	
	start=clock();
	linstraightradix(a,n,32,11);
	ende=clock();
	printf("Lin. Straight Radix:\t %6.3f\n",(ende-start)/(float)CLOCKS_PER_SEC);
	for(i=0; i<n; i++){
		//printf("%d, ",a[i]);
	        a[i]=c[i];
	}
	//printf("\b\b  \n\n");
	
	free(a);
	free(c);
	free(b);
	return 0;
}