/*
 * =====================================================================================
 *
 *       Filename:  sort_cmp.c
 *    Description:  Porownanie szybkosci sortowania przez wstawianie i przez wybieranie.
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define MAX 50000

/*  Funkcja losuje 'n' liczb losowych z zakresu 0-1000 i umieszcza je w tablicy 't'. */
float *losuj(float t[], int n)
{
   int i=0;
   while(i<n)
   {
      t[i]=((rand() * 1.0 )/RAND_MAX)*1000;
      i=i+1;
   }
   return t;
}

/* Funkcja wyswietla na terminalu 'n' pierwszych elementow tablicy 't'.  */
void wyswietl(float t[], int n)
{
   int i;
   i=0;
   while(i<n)
   {
      printf("%f\n",t[i]);
      i=i+1;
   }
}

/*  Funkcja zwraca pozycje w tablicy 't[]' elementu o najwiekszej wartosci. */
int maxind(float t[], int n)
{
   int k=0;
   int i=1;
   
   while(i<n)
   {
      if( t[i] > t[k] ) k=i; 
      i=i+1;
   }
   return k;
}

/*  Funkcja sortuje elementy w tablicy algorytmem przez wybieranie (selection sort).  */
void sortowanie_przez_wybieranie(float t[], int n)
{
   int k, i=0;
   float x;

   while(i<n-1)
   {
      k=maxind(t,n-i);
      
      x=t[n-i-1];
      t[n-i-1] = t[k];
      t[k]=x;

      i=i+1;
   }
}


/*  Funkcja sortuje elementy w tablicy algorytmem przez wstawianie (insert sort).  */
void sortowanie_przez_wstawianie(float t[], int n)
{
   int k, i=1;
   float x;

   while(i<n)
   {
      x=t[i];
      k=i;
      while( k> 0 && x < t[k-1] )
      {
         t[k] = t[k-1];
         k = k - 1;
      }
      t[k] = x;
      i=i+1;
   }
}

/*  Funkcja kopiuje liczby z tablicy 't1' do tablicy 't2'. */
void copy(const float *t1, float *t2, int n)
{
   int i=0;
   while(i<n)
   {
      t2[i]=t1[i];
      i = i + 1;
   }
}


int main()
{
   float tab[MAX],tab2[MAX];
   float x;
   clock_t tik, tak;
   float t1;
   int n,i ;

   printf("Porownanie szybkosci algoorytmow sortowania.\n");
   printf( "Podaj liczbe elementow do posortowania (max %d)\n",MAX);

   srand(time(0));
   
   printf("n=");
   scanf("%d",&n);
   

   printf("\twybieranie  wstawianie\n\t---------------------\n");
   printf("losowe  : ");
   
   losuj(tab,n);
   copy(tab,tab2,n);
   tik=clock();
   sortowanie_przez_wybieranie(tab,n);
   tak=clock();
   t1=((float)(tak-tik)/CLOCKS_PER_SEC);
   printf("%f    ", t1);

   tik=clock();
   sortowanie_przez_wstawianie(tab2,n);
   tak=clock();
   t1=((float)(tak-tik)/CLOCKS_PER_SEC);
   printf("%f\n", t1);

   printf("rosnace : ");
   copy(tab,tab2,n);
     
   tik=clock();
   sortowanie_przez_wybieranie(tab,n);
   tak=clock();
   t1=((float)(tak-tik)/CLOCKS_PER_SEC);
   printf("%f    ", t1);

   tik=clock();
   sortowanie_przez_wstawianie(tab2,n);
   tak=clock();
   t1=((float)(tak-tik)/CLOCKS_PER_SEC);
   printf("%f\n", t1);



   printf("malejace: ");
   
   i=0;
   while(i<n/2)
   {
      x=tab[i];
      tab[i]=tab[n-i-1];
      tab[n-i-1]=x;
      i=i+1;
   }


   copy(tab,tab2,n);
     
   tik=clock();
   sortowanie_przez_wybieranie(tab,n);
   tak=clock();
   t1=((float)(tak-tik)/CLOCKS_PER_SEC);
   printf("%f    ", t1);

   tik=clock();
   sortowanie_przez_wstawianie(tab2,n);
   tak=clock();
   t1=((float)(tak-tik)/CLOCKS_PER_SEC);
   printf("%f\n", t1);
   return 0;  
}