Untitled

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <limits.h>

#define F_RANDOM 0
#define F_CONSTANT 1
#define F_ASC 3
#define F_DESC 4
#define F_ASCDESC 5
#define F_DESCASC 6

void fillTable(int* tab, unsigned int size,  int type)
{
     int i, j, x;
     x=0;

     switch(type)
     {
                 case F_RANDOM:
                      srand( (unsigned)time(NULL));
                      for(i=0; i<size; i++)
                      {
                         tab[i] = rand()%50;
                      }
                      break;

                 case F_CONSTANT:
                      for(i=0; i<size; i++)
                      {
                         tab[i] = 0;
                      }
                      break;

                 case F_ASC:
                      for(i=0; i<size; i++)
                      {
                         tab[i] = i;
                      }
                      break;

                 case F_DESC:
                      for(i=0; i<size; i++)
                      {
                          tab[i] = size-i;
                      }
                      break;
                 case F_ASCDESC:
                      for(i=0; i<size/2; i++)
                      {
                          tab[i] = 2*i+1;
                      }

                      for(i=size/2; i<size; i++)
                      {
                          tab[i] = 2*(size-1-i);
                      }
                      break;
                 case F_DESCASC: // TODO
                      x = size/2;
                      for(i=0; i<size/2; i++)
                      {
                          tab[i] =  2*(size-1-x);
                          x++;

                      }
                      x = 0;
                      for(i=size/2; i<size; i++)
                      {
                          tab[i] = 2*x+1;
                          x++;
                      }
                      break;
     }
}


void ShellSort(int* tab, int n)
{
     int buf, i,  j, jump = 1;
     while ( jump < n )
     {
           jump = 3*jump + 1;
     }
     while(jump > 0)
     {
                for( i = jump; i<n; i++)
                {
                     buf = tab[i];
                     for(j=i-jump; j>=0 && buf < tab[j]; j-=jump)
                     {
                                   tab[j+jump] = tab[j];
                     }
                     tab[j+jump] = buf;
                }
                jump /= 3;
     }
}

/*void countingSort(int* tab, int n)
{
     int i, max = tab[0];
     unsigned int sum;
     for(i=1; i<n; i++)
     {
              if(tab[i] > max)
                 max = tab[i];
     }
     max += 1;

     int* B = (int*)malloc(max*sizeof(int));
     int* C = (int*)malloc((max)*sizeof(int));
     int* D = (int*)malloc(n*sizeof(int));

     for(i=0; i<max; i++)
     {
       B[i] = 0;
       C[i] = 0;
       D[i] = 0;
     }

     for(i=0; i<n; i++)
     {
       B[tab[i]]++;
     }
     sum = B[0];
     for(i=1; i<max; i++)
     {
              C[i] = sum + B[i];
              sum+= B[i];

              printf("%d ", C[i]);
     }


     for( i= n-1; i>=0; i--)
     {
          C[tab[i]] // todo
     }


     free(B);
     free(C);
     free(D);
}
    */
// 2001-cs-1902.. Rao Hammad Aslam... Counting Sort algo


void count_sort( int* arr, int n)
  {

     int i;
     int max = arr[0];
     for(i = 0; i<= n; i++)
         if( max < arr[i] )
             max = arr[i];

    int *temp;
    temp = (int*)malloc(max*sizeof(int));

    for ( i = 0; i<= max; i++)
      temp[i] = 0;

    for (i = 0; i<= n; i++)
        temp[arr[i]] =temp[arr[i]] + 1;
    // Step 4: Change the elements of the new array to be the Cumulative Sum

     for (i = 1; i<= max; i++)
                 temp[i] = temp[i - 1] + temp[i];


    // Step 5:
    //       - Make another array of size similar to A:
    //       - Start with the last element of A.. and place it at the
    //        location of new array B which is mentioned in array temp.
    int *new_arr;

    new_arr = (int*)malloc(n*sizeof(int));
     // initialize new array
        for ( i = n; i>=0; i-- )
        new_arr[i] = 0;

    for ( i = n; i>=0; i--)
        {// place the element in the required location
                new_arr[ temp[ arr[i] ] - 1] = arr[i];
        // decrement the frequency of element! to record that it has been placed one time
            temp[arr[i]] = temp[arr[i]] - 1;
   }
 // Step 6: Copy the new_arr[] which is now sorted into the actual array:
    for( i=0; i<=n; i++)
           arr[i] = new_arr[i];
 }


int main()
{
    // ------------TEST--------------------------
    srand((unsigned)time(NULL));

    unsigned long int i;
    LARGE_INTEGER ticksPerSecond, tick, start_ticks, end_ticks, cputime;
    if(!QueryPerformanceFrequency(&ticksPerSecond))
      exit(1);

     const int k = 17;

     int* tab = (int*)malloc(k*sizeof(int));
     fillTable(tab, k, F_RANDOM);

     for(i=0; i<k; i++) printf("%d ", tab[i]);

     printf("\n------------------------\n");


     count_sort(tab, k-1);
     for(i=0; i<k; i++) printf("%d ", tab[i]);

     printf("\n------------------------\n");

     //countingSort(tab, 20);
     system("pause");


    FILE *fp;


    if((fp=fopen("testy.txt", "w")) == NULL) { printf("Error"); exit(1); }


    for(i=10000; i<=1000000; i+=5000)
    {
       int* tab = (int*)malloc(i*sizeof(int));
       fillTable(tab, i, F_RANDOM);


       QueryPerformanceCounter(&start_ticks);
       ShellSort(tab, i);
       QueryPerformanceCounter(&end_ticks);
       printf("%lu\n", i);
       cputime.QuadPart = end_ticks.QuadPart - start_ticks.QuadPart;

       fprintf(fp, "%10.9f\n", ((float)cputime.QuadPart/(float)ticksPerSecond.QuadPart));
       free(tab);
    }


    fclose(fp);

    // ------------TEST--------------------------


    return 0;
}