//Lubna Yaghmoure 1071380

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#define MAX 20
#define N   100000
#define NUMELTS 100
#define LeftChild( i )  ( 2 * ( i ) + 1 )
#define Cutoff ( 3 )
#define Error( Str )        FatalError( Str )
#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )

void MenuSortAlgorithms();
int  MenuSort();
void BubbleSort(char *x[], int y);
void Swap(char **Lhs,char **Rhs);
void InsertionSort(char *x[], int Y);
void Shellsort( char *x[ ], int Y );
void PercDown( char *A[ ], int i, int Y );
void Heapsort( char *A[ ], int Y );
void Merge(char *A[ ],char *TmpArray[ ],int Lpos, int Rpos, int RightEnd );
void MSort(char *A[ ],char *TmpArray[ ],int Left, int Right );
void Mergesort(char *A[ ], int Y );
char* Median3( char *A[ ], int Left, int Right );
void Qsort(char *A[ ], int Left, int Right );
void Quicksort( char *A[ ], int Y );
void radixsort(char *A[ ],int Y);


int main()
{

    MenuSortAlgorithms();
    printf("Quittting!!!\n");
    return 0;
}





void MenuSortAlgorithms()
{
//bool loop = true;
int choice;
char FileName[10];
FILE *inp,*out;
time_t end,start;
char word[MAX];
char *x[N];
int n = 0;
int i=0;

/* open file */
printf("Enter input file name \n");
for(scanf("%s",FileName);(inp=fopen(FileName,"r"))==NULL;scanf("%s",FileName))
{
    printf("Error cant find %s file\n",FileName);
    printf("Re-Enter file name\n");
}

printf("Enter output file name \n");
for(scanf("%s",FileName);(out=fopen(FileName,"w"))==NULL;scanf("%s",FileName))
{
    printf("Error cant find %s file\n",FileName);
    printf("Re-Enter file name\n");
}

printf("done1");

while (feof(inp)==0)
{
  for(i = 0; fscanf(inp,"%s",word)!=EOF; ++i)
  {
   x[i] = (char *)calloc(strlen(word)+1, sizeof(char));
   strcpy(x[i], word);
  }
}

n = i;



while(1)
  {
    choice = MenuSort();
    switch (choice)
    {
      case 1:{
              start=time(NULL);
              BubbleSort(x,n);
              end=time(NULL);

              for(i=0;i<n; ++i)
             {
                   printf("%s  ",x[i]);
                   fprintf(out,"%s  ",x[i]);
             }
               fprintf(out,"\nBubble sort used %3.12f seconds.\n", difftime(end, start));
               printf("\nBubble sort used %3.12f seconds.\n", difftime(end, start));
             }
             break;

      case 2:{
              start=time(NULL);
              InsertionSort(x,n);
              end=time(NULL);
              for(i=0;i<n; ++i)
             {
                   printf("%s  ",x[i]);
                   fprintf(out,"%s  ",x[i]);
             }
               fprintf(out,"Insertion sort used %3.20f seconds.\n", difftime(end, start));
               printf("Insertion sort used %3.20f seconds.\n", difftime(end, start));
             }
            break;

      case 3:{
              start=time(NULL);
              Shellsort(x,n);
              end=time(NULL);

              for(i=0;i<n; ++i)
             {
                   printf("%s  ",x[i]);
                   fprintf(out,"%s  ",x[i]);
             }
               fprintf(out,"Shell sort used %10.200f seconds.\n", difftime(end, start));
               printf("Shell sort used %10.200f seconds.\n", difftime(end, start));
             }
             break;

      case 4:{
              start=time(NULL);
              Heapsort(x,n);
              end=time(NULL);

              for(i=0;i<n; ++i)
             {
                   printf("%s  ",x[i]);
                   fprintf(out,"%s  ",x[i]);
             }
               fprintf(out,"Heap sort used %3.12f seconds.\n", difftime(end, start));
               printf("Heap sort used %3.12f seconds.\n", difftime(end, start));
             }
             break;

      case 5:{
              start=time(NULL);
              Mergesort(x,n);
              end=time(NULL);

              for(i=0;i<n; ++i)
             {
                   printf("%s  ",x[i]);
                   fprintf(out,"%s  ",x[i]);
             }
               fprintf(out,"Merge sort used %3.20f seconds.\n", difftime(end, start));
               printf("Merge sort used %3.20f seconds.\n", difftime(end, start));
             }
             break;
      case 6:{
              start=time(NULL);
              Quicksort(x,n);
              end=time(NULL);
              for(i = 0; i < n; ++i)
               {
                   printf("%s  ", x[i]);
                   fprintf(out,"%s  ", x[i]);
               }
               fprintf(out,"Quick sort used %10.200f seconds.\n", difftime(end, start));
               printf("Quick sort used %10.200f seconds.\n", difftime(end, start));
             }
             break;
             case 7:{
              start=time(NULL);
              radixsort(x,n);
              end=time(NULL);
              for(i = 0; i < n; ++i)
               {
                   printf("%s  ", x[i]);
                   fprintf(out,"%s  ", x[i]);

               }
               fprintf(out,"Radix sort used %3.20f seconds.\n", difftime(end, start));
               printf("Radix sort used %3.20f seconds.\n", difftime(end, start));
             }break;

case 8:{
 exit(0);
 }
 break;


    }
  }
/* Close file */
fclose(inp);
fclose(out);
}

int MenuSort()
{
    int temp;
do{
    printf ("\n****Sort Algorithms*****\n" );
    printf("Choose one of the sort Algorithms from the list Below :: ENTER CHOICE FROM (1-8)\n" );
    printf("1. Bubble Sort\n");
    printf("2. Insertion Sort\n");
    printf("3. shell Sort\n");
    printf("4. Heap Sort\n");
    printf("5. Merge Sort\n");
    printf("6. Quick Sort\n");
    printf("7. Radix Sort\n");
    printf("8. Quit Sort .\n");
    printf("------------------------------------------------------\n");
    scanf("%d",&temp);

}while((temp != 1)&&(temp != 2)&&(temp != 3)&&(temp != 4)&&(temp != 5)&&(temp != 6)&&(temp != 7)&&(temp != 8)&&(temp != 9));
    return temp;
}

void  Swap( char **Lhs,char **Rhs )
{
            char *Tmp = *Lhs;
            *Lhs = *Rhs;
            *Rhs = Tmp;
}

void BubbleSort(char *x[], int y) {
 int i = 0;
 int j = 0;
 for(i = 0; i < y; ++i)
  for(j = i + 1; j < y; ++j)
   if(strcmp(x[i], x[j]) > 0)
     Swap(&x[i], &x[j]);
}

void InsertionSort( char *x[], int Y )
{
    int j, P;
    char *Tmp;

    for( P = 1; P < Y; P++ )
   {
          Tmp = x[ P ];
          for( j = P; j > 0 && strcmp(x[ j - 1 ], Tmp)>0; j-- )
              x[ j ] = x[ j - 1 ];
          x[ j ] = Tmp;
   }
}

void Shellsort( char *x[ ], int Y )
{
int i, j, Increment;
char *Tmp;

for( Increment = Y / 2; Increment > 0; Increment /= 2 )
    for( i = Increment; i < Y; i++ )
    {
    Tmp = x[ i ];
    for( j = i; j >= Increment; j -= Increment )
     if( strcmp(Tmp , x[ j - Increment ] )<0)
        x[ j ] = x[ j - Increment ];
     else
        break;
     x[ j ] = Tmp;
    }
}

void PercDown( char *A[ ], int i, int Y )
{
            int Child;
            char *Tmp;

      for( Tmp = A[ i ]; LeftChild( i ) < Y; i = Child )
            {
          Child = LeftChild( i );
         if( Child != Y - 1 && strcmp(A[ Child + 1 ] , A[ Child ])>0 )
          Child++;printf("00\n");
          if( strcmp(Tmp , A[ Child ] )<0)
              A[ i ] = A[ Child ];
                else
              break;
            }
      A[ i ] =Tmp;

      printf("Worked1\n");
}

void Heapsort( char *A[ ], int Y )
{
 int i;

      for( i = Y / 2; i >= 0; i-- )  /* BuildHeap */
          PercDown( A, i, Y );
      //printf("worked0");
      for( i = Y - 1; i > 0; i-- )
     {
         Swap( &A[ 0 ], &A[ i ] );  /* DeleteMax */
          PercDown( A, 0, i );
    }
     //printf("Worked2\n");
}

void Merge(char *A[ ],char *TmpArray[ ],int Lpos, int Rpos, int RightEnd )
{
int i, LeftEnd, NumElements, TmpPos;

LeftEnd = Rpos - 1;
TmpPos = Lpos;
NumElements = RightEnd - Lpos + 1;

/* main loop */
while( Lpos <= LeftEnd && Rpos <= RightEnd )
  if( strcmp(A[ Lpos ] , A[ Rpos ])<=0 )
    strcpy(TmpArray[ TmpPos++ ] , A[ Lpos++ ]);
 else
    strcpy(TmpArray[ TmpPos++ ] ,A[ Rpos++ ]);
while( Lpos <= LeftEnd )  /* Copy rest of first half */
   strcpy(TmpArray[ TmpPos++ ] , A[ Lpos++ ]);
while( Rpos <= RightEnd ) /* Copy rest of second half */
    strcpy(TmpArray[ TmpPos++ ],A[ Rpos++ ]);

/* Copy TmpArray back */
for( i = 0; i < NumElements; i++, RightEnd-- )
  strcpy( A[ RightEnd ],TmpArray[ RightEnd ]);

//printf("Worked1\n");
}

void MSort(char *A[ ],char *TmpArray[ ],int Left, int Right )
{
 int Center;

     if( Left < Right )
    {
      Center = ( Left + Right ) / 2;
      MSort( A, TmpArray, Left, Center );
      MSort( A, TmpArray, Center + 1, Right );
      Merge( A, TmpArray, Left, Center + 1, Right );
    }

//printf("Worked2\n");
}

void Mergesort(char *A[ ], int Y )
{
 char *TmpArray[Y];
  int i=0;
  for(i=0;i<Y;i++)
    TmpArray[i] =( char* ) malloc( sizeof( char *) );

    if( TmpArray != NULL )
    {
     MSort( A,TmpArray, 0, Y - 1 );
     free( TmpArray );
    }
    else
     FatalError( "No space for tmp array!!!" );

//printf("Worked3\n");
}

 /* Return median of Left, Center, and Right */
 /* Order these and hide the pivot */

char* Median3( char *A[ ], int Left, int Right )
{
            int Center = ( Left + Right ) / 2;

            if( strcmp(A[ Left ],A[ Center ] )>0)
                Swap( &A[ Left ], &A[ Center ] );
            if( strcmp(A[ Left ] , A[ Right ] )>0)
                Swap( &A[ Left ], &A[ Right ] );
            if( strcmp(A[ Center ],A[ Right ])>0 )
                Swap( &A[ Center ], &A[ Right ] );

            /* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */

            Swap( &A[ Center ], &A[ Right - 1 ] );  /* Hide pivot */
            return A[ Right - 1 ];                /* Return pivot */
}


void Qsort(char *A[ ], int Left, int Right )
{
 int i, j;
 char *Pivot;

 if( Left + Cutoff <= Right )
{
 Pivot = Median3( A, Left, Right );
 i = Left; j = Right - 1;
 for( ; ; )
{
    while( strcmp(A[ ++i ] , Pivot)<0 ){ }
     while(strcmp( A[ --j ] , Pivot )>0){ }
        if( i < j )
         Swap( &A[ i ], &A[ j ] );
        else
         break;
}
 Swap( &A[ i ], &A[ Right - 1 ] );  /* Restore pivot */
 Qsort( A, Left, i - 1 );
 Qsort( A, i + 1, Right );
}
 else  /* Do an insertion sort on the subarray */
    InsertionSort( A + Left, Right - Left + 1 );
}

void Quicksort( char *A[ ], int Y )
{
    Qsort( A, 0, Y - 1 );
}


void radixsort(char *a[],int n)
{
 int rear[10],front[10],first,p,q,exp,k,i,j;
 char *y;
 struct
 {
  char *info;
  int next;
 }node[NUMELTS];
 for(i=0;i<n-1;i++)
 {
  strcpy(node[i].info,a[i]);
  node[i].next=i+1;
 }
 strcpy(node[n-1].info,a[n-1]);
 node[n-1].next=-1;
 first=0;

  for(k=1;k<=2;k++)      //consider only 2 digit number
  {
   for(i=0;i<10;i++)
     {
      front[i]=-1;
      rear[i]=-1;
     }

    while(first!=-1)
      {
       p=first;
       first=node[first].next;
       strcpy(y,node[p].info);
       exp=(int)pow(10,k-1);
       j=((int)y/exp)%10;
       q=rear[j];
       if(q==-1)
	 front[j]=p;
       else
	 node[q].next=p;
       rear[j]=p;
      }
    for(j=0;j<10&&front[j]==-1;j++)
     ;
    first=front[j];
    while(j<=9)
     {
      for(i=j+1;i<10&&front[i]==-1;i++)
       ;
      if(i<=9)
      {
	p=i;
	node[rear[j]].next=front[i];
      }
      j=i;
    }
    node[rear[p]].next=-1;
}
//copy into original array
for(i=0;i<n;i++)
{
  strcpy(a[i],node[first].info);
  first=node[first].next;

}
}