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

int *genCGPA ( int n )
{
   double x;
   int *A, i;

   A = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) {
      x = (double)rand() / (double)RAND_MAX;
      if (x <= 0.05) A[i] = rand() % 101;
      else if (x <= 0.25) A[i] = 101 + rand() % 100;
      else if (x <= 0.85) A[i] = 201 + rand() % 200;
      else A[i] = 401 + rand() % 100;
   }
   return A;
}

int *cpyCGPA ( int *A, int n )
{
   int *B, i;

   B = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) B[i] = A[i];
   return B;
}

/* On large data sets with only a few (like 501) different possible values,
   this implementation of quick sort is essentially a linear-time algorithm. */
void quicksort ( int *A, int n )
{
   int i, j, k, pivot, t;

   if (n <= 1) return;
   pivot = A[0];
   i = 0; j = 1; k = n-1;
   while (j <= k) {
      if (A[j] == pivot) ++j;
      else if (A[j] < pivot) {
         t = A[i]; A[i] = A[j]; A[j] = t; ++i; ++j;
      } else {
         t = A[j]; A[j] = A[k]; A[k] = t; --k;
      }
   }
   quicksort(A, i);
   quicksort(A+j, n-j);
}

void countingsort1 ( int *A, int n )
{
   int *B, *C, i, j, s, t;

   C = (int *)malloc(501 * sizeof(int));
   for (j=0; j<=500; ++j) C[j] = 0;

   for (i=0; i<n; ++i) ++C[A[i]];
   t = C[0]; C[0] = 0;
   for (j=1; j<=500; ++j) {
      s = C[j]; C[j] = C[j-1] + t; t = s;
   }
   B = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) {
      j = A[i];
      B[C[j]] = j;
      ++C[j];
   }
   for (i=0; i<n; ++i) A[i] = B[i];
   free(C); free(B);
}

void countingsort2 ( int *A, int n )
{
   int *C, i, j, k;

   C = (int *)malloc(501 * sizeof(int));
   for (j=0; j<=500; ++j) C[j] = 0;

   for (i=0; i<n; ++i) ++C[A[i]];

   i = 0;
   for (j=0; j<500; ++j) for (k=0; k<C[j]; ++k) A[i++] = j;
   for(; i<n; ++i) A[i] = 500;

   free(C);
}

void cmpCGPA ( int *A, int *B, int n )
{
   int i;

   for (i=0; i<n; ++i) if (A[i] != B[i]) {
      printf("*** Arrays differ in position %d\n", i);
      return;
   }
   printf("+++ Two arrays are identical\n");
}

int main ( int argc, char *argv[] )
{
   int n, *A, *B, *C;
   clock_t c1, c2;

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   srand((unsigned int)time(NULL));

   c1 = clock(); A = genCGPA(n); B = cpyCGPA(A,n); C = cpyCGPA(A,n); c2 = clock();
   printf("+++ Array generation time = %10.6lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   c1 = clock(); quicksort(A,n); c2 = clock();
   printf("+++ Quick sort time       = %10.6lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   c1 = clock(); countingsort1(B,n); c2 = clock();
   printf("+++ Counting sort 1 time  = %10.6lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   c1 = clock(); countingsort2(C,n); c2 = clock();
   printf("+++ Counting sort 2 time  = %10.6lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   cmpCGPA(A,B,n); cmpCGPA(A,C,n);

   free(A); free(B); free(C);
   exit(0);
}