#include <iostream>
#include <cstdlib>
#include <ctime>
#include <memory>
using namespace std;

/*****    Sortier Header ****/

int compare( const void* arg1, const void* arg2 ) { 
	// Vergleichsfunktion für Integer
	return *(int*) arg1 - *(int*) arg2;
} 

typedef int intar[];	

// Schnittstelle A ist ein Array von A[0] bis A[max]
// d.h. mit max+1 Elementen  

void InitIntAr (intar A, int max); 
 // Initialisiere das Array A mit zufälligen Werten

void CopyIntAr (intar Quelle, intar Ziel, int max); 
 // // Kopiere Quelle -> Ziel

int TestAr (intar A, int max); 
 // Teste ob die Elemente des Array A sortiert sind


void InsertionSort (intar A, int max); 
void ShellSort (intar A, int max);
void DistributionSort (intar A, int max); 

/*****    Ende Sortier Header ****/

/*****    Sortier Main ****/



const int maxIndex = 5000000;        // maximaler Index von A	 
typedef int intA[maxIndex+1];   // A[0] .. A[max]
intA A,B;
int* ip = A;
clock_t clStart, clStop;
double Laufzeit;

void main () {
cout.precision(8);
cout << "Sort-Tester: Anfang." << endl;
InitIntAr(B, maxIndex);

cout << endl << "Kopiere B -> A" << endl;
CopyIntAr(B, A, maxIndex);
if ( !TestAr(A,maxIndex) )  cout << "Teste-A: A ist noch nicht sortiert! " << endl;
cout << "Shell-Sort des Array A. Elemente: " << maxIndex  << endl;

clStart = clock();
ShellSort(A,maxIndex);
clStop  = clock();
Laufzeit = double(clStop - clStart) / double(CLOCKS_PER_SEC);
if ( TestAr(A,maxIndex) )  cout << "Teste-A: ok - A ist jetzt sortiert! " << endl;
else                       cout << "Teste-A: Fehler - A ist nicht sortiert!!! " << endl;
cout << "Laufzeit: " << Laufzeit << endl;

cout << endl << "Kopiere B -> A" << endl;
CopyIntAr(B, A, maxIndex);
if ( !TestAr(A,maxIndex) )  cout << "Teste-A: A ist noch nicht sortiert! " << endl;
cout << "Distribution-Sort des Array A. Elemente: " << maxIndex  << endl;

clStart = clock();  
DistributionSort(A,maxIndex);
clStop  = clock();
Laufzeit = double(clStop - clStart) / double(CLOCKS_PER_SEC);
if ( TestAr(A,maxIndex) )  cout << "Teste-A: ok - A ist jetzt sortiert! " << endl;
else                       cout << "Teste-A: Fehler - A ist nicht sortiert!!! " << endl;
cout << "Laufzeit: " << Laufzeit << endl;

cout << endl << "Kopiere B -> A" << endl;
CopyIntAr(B, A, maxIndex);
if ( !TestAr(A,maxIndex) )  cout << "Teste-A: A ist noch nicht sortiert! " << endl;
cout << "cpp Q-Sort des Array A. Elemente: " << maxIndex  << endl;

clStart = clock();  
qsort(ip, (size_t) (maxIndex+1), sizeof(int), compare); 
clStop  = clock();
Laufzeit = double(clStop - clStart) / double(CLOCKS_PER_SEC);
if ( TestAr(A,maxIndex) )  cout << "Teste-A: ok - A ist jetzt sortiert! " << endl;
else                       cout << "Teste-A: Fehler - A ist nicht sortiert!!! " << endl;
cout << "Laufzeit: " << Laufzeit << endl;
 

cout << "Sort-Tester: fertig." << endl;

}

/*****    Ende Sortier Main ****/

/*****    Anfang Sortier Implementierer ****/


// Schnittstelle A ist ein Array von A[0] bis A[max]
// d.h. mit max+1 Elementen  

void InitIntAr (intar A, int max) 
{ // Initialisiere das Array A mit zufälligen Werten
srand(42); // seed
for (int i = 0; i <= max; i++) A[i] = rand();
}

void CopyIntAr (intar Quelle, intar Ziel, int max) 
{ // Kopiere Quelle -> Ziel
  // for (int i = 0; i <= max; i++) Ziel[i] = Quelle[i];
  memcpy(Ziel, Quelle, (max+1)*sizeof(int));
}


int TestAr (intar A, int max) 
{ // Initialisiere ob die Elemente des Array A sortiert sind
int erg = 1;
for (int i = 0; i < max; i++) if (A[i] > A[i+1]) {erg =0; break;};
return erg;
}


void InsertionSort (intar A, int max) 
{  for ( int k = 1; k <= max; k++ )
     { if ( A[k] < A[k-1]) 
        {	int x  = A[k];
    		for (int i = k; ( (i > 0) && (A[i-1]> x) ); i--)
               A[i] = A[i-1];
         	A[i] = x;
        }
      };    
}

void ShellSort (intar A, int max) 
{ int hmax, h ;
  for (	hmax = 1; hmax < max ; hmax = 3*hmax+1 );
  for ( h = hmax/3; h >= 1; h /= 3) 
    for ( int k = h; k <= max; k++ )
     {
        if ( A[k] < A[k-h]) 
        {	int x  = A[k];
    		for (int i = k; ( (i > (h-1)) && (A[i-h]> x) ); i-=h)
                A[i] = A[i-h];
         	A[i] = x;
        }
      };    
}

inline int By1 (int x) { return (  x        & 0xff); }
inline int By2 (int x) { return ( (x >>  8) & 0xff); }
inline int By3 (int x) { return ( (x >> 16) & 0xff); }
inline int By4 (int x) { return ( (x >> 24) & 0xff); }


void DistributionSort (intar A, int max) 
{ int Count[256];
  int i;

  typedef int* intP;	
  // intarPtr B = intarPtr(calloc(max+1, sizeof(int)));
  intP B = new int[max+1];
  CopyIntAr (A, B, max);
  

  // Byte 1
  for (i=0; i < 256; i++) Count[i] = 0;
  for (i=0; i <= max; i++) // Zählen
      (Count[ A[i] & 0xff ])++;
  for (i=1; i < 256; i++) // Aufsummieren
       Count[i] += Count[i-1];
  for (i=max; i >= 0; i--) // Verteilen
		B[--(Count[A[i] & 0xff])] = A[i];
	  
  CopyIntAr (B, A, max);
   

  // Byte 2
  for (i=0; i < 256; i++) Count[i] = 0;
  for (i=0; i <= max; i++) // Zählen
      (Count[ (A[i] >>  8) & 0xff ])++;
  for (i=1; i < 256; i++) // Aufsummieren
       Count[i] += Count[i-1];
  for (i=max; i >= 0; i--) // Verteilen
      B[--(Count[(A[i] >>  8) & 0xff])] = A[i];
  CopyIntAr (B, A, max);

  // Byte 3
  for (i=0; i < 256; i++) Count[i] = 0;
  for (i=0; i <= max; i++) // Zählen
      (Count[ (A[i] >> 16) & 0xff ])++;
  for (i=1; i < 256; i++) // Aufsummieren
       Count[i] += Count[i-1];
  for (i=max; i >= 0; i--) // Verteilen
      B[--(Count[(A[i] >> 16) & 0xff])] = A[i];
  CopyIntAr (B, A, max);

  // Byte 4
  for (i=0; i < 256; i++) Count[i] = 0;
  for (i=0; i <= max; i++) // Zählen
      (Count[ (A[i] >> 24) & 0xff ])++;
  for (i=1; i < 256; i++) // Aufsummieren
       Count[i] += Count[i-1];
  for (i=max; i >= 0; i--) // Verteilen
     B[--(Count[(A[i] >> 24) & 0xff])] = A[i];
  CopyIntAr (B, A, max);

}