/* Esempio di quick sort e bubble sort */
/* versione corretta (forse) */
/* allocazione dinamica della memoria */
/* ho aggiunto mergesort ma e' ancora da terminare (ovvero non funziona) */

#include<stdio.h>

#include <stdlib.h>

#include<time.h>



void bubble_sort(int*);
void quick_sort(int*,int,int);
void merge_sort(int*,int,int);
void fuse(int*,int,int,int);
void scambia(int *,int *);
static int nitems;

int main(int argc, char **argv)
{
clock_t start,stop;
int *listab, *listaq, *listam;
double bubble, quick;

int ii;

if(argc!=2)
 {
  printf("Numero di argomenti sbagliato: devi darmi il numero di iterazioni\n");
  exit(1);
 }

nitems = atoi(argv[1]);
/* non faccio controllo di errore */

if((listab=malloc(nitems*sizeof(int)))==NULL)
 {
  fprintf(stderr,"Attenzione non riesco ad allocare memoria file %s linea %d\n",__FILE__,__LINE__);
  perror("errore: ");
  exit(1);
 }

if((listaq=malloc(nitems*sizeof(int)))==NULL)
 {
  fprintf(stderr,"Attenzione non riesco ad allocare memoria file %s linea %d\n",__FILE__,__LINE__);
  perror("errore: ");
  exit(1);
 }

if((listam=malloc(nitems*sizeof(int)))==NULL)
 {
  fprintf(stderr,"Attenzione non riesco ad allocare memoria file %s linea %d\n",__FILE__,__LINE__);
  perror("errore: ");
  exit(1);
 }

printf("Ordino %d elementi\n",nitems);

for(ii=0;ii<nitems;ii++)
 {
  listab[ii]=listaq[ii]=listam[ii]=rand()/100000;
 }

start=clock();
bubble_sort(listab);
stop=clock();
bubble=(double)stop-start;

start=clock();
quick_sort(listaq,0,nitems-1);
stop=clock();
printf("\n");
quick=(double)stop-start;

start=clock();
merge_sort(listam,0,nitems-1);
stop=clock();


printf("\nTempo di esecuzione bubble sort: %g\n",bubble/CLK_TCK);
printf("Tempo di esecuzione quick sort: %g\n",quick/CLK_TCK);
printf("Tempo di esecuzione merge sort: %g\n",((double)stop-start)/CLK_TCK);

#ifdef DEBUG

for(ii=0;ii<nitems;ii++)
 {
 if((listab[ii]!=listaq[ii])||(listab[ii]!=listam[ii]))fprintf(stderr,"WARNING\n");
 printf("%d -- %d -- %d\n",listab[ii],listaq[ii],listam[ii]);
 }
#endif

return 0;
}

void bubble_sort(int *a)
{
int ii;
int scambio=0;
int last=nitems;

while(!scambio)
 {
 printf(".");
 scambio=1;
 for(ii=1;ii<last;ii++)
  if(a[ii-1]>a[ii])
   {
    scambia(&a[ii],&a[ii-1]);
    scambio=0;
   }
 last--;
 }
 printf("\n");
}

void quick_sort(int *a, int sinistra, int destra)
{
 int ii,jj;
 int pivot;
 
 printf("#");
 pivot=a[sinistra];
 jj=sinistra+1;
 ii=destra;
 
 while(ii>=jj)
 {
  while((jj<=destra)&&(a[jj]<=pivot))
   jj++;
  while((a[ii]>pivot)||(ii==jj))
   ii--;
  if(ii>jj)
   scambia(&a[ii],&a[jj]);
 }
 if(ii!=sinistra)
  scambia(&a[ii],&a[sinistra]);
 if(sinistra<(ii-1))
  quick_sort(a, sinistra, ii-1);
 if(destra>jj)
  quick_sort(a, jj, destra);
}

void merge_sort(int *a, int indice_basso, int indice_alto)
{
int indice_di_mezzo;

printf("$");

/* se sono uguali significa che la lista e' composta da un singolo elemento */
if(indice_alto==indice_basso)return;

/* calcolo qual'e' l'indice dell'elemento a meta' (circa) dell'array */
indice_di_mezzo=(indice_alto-indice_basso)/2+indice_basso;
/* potrei ottenere anche semiliste composte da un singolo elemento */
merge_sort(a, indice_basso, indice_di_mezzo);
merge_sort(a, indice_di_mezzo+1, indice_alto);

/* a questo punto le due semiliste sono gia' ordinate,
 * basta fonderle */
fuse(a, indice_basso, indice_di_mezzo, indice_alto);
}

void fuse(int *a, int low_index, int middle_index, int high_index)
{
 int *tmp_arr=NULL;
 /* fisso due indici che usero' per scandire i due semiarray */
 int median_index=middle_index;
 /* il seguente e' il numero degli elementi -1 */
 int tmp_index=high_index-low_index;
 int numel=tmp_index+1;
 
/* alloco un array temporaneo in cui ordinare i due semiarray */
if((tmp_arr=malloc((tmp_index+1)*sizeof(int)))==NULL)
 {
  fprintf(stderr,"Attenzione non riesco ad allocare memoria file %s linea %d\n",__FILE__,__LINE__);
  perror("errore: ");
  exit(1);
 }

/* scandisco i semiarray fino a che non ne esaurisco uno */
while((high_index>=(middle_index+1))&&(median_index>=low_index))
 {
  /* confronto gli elementi piu' alti dei due semiarray */
  if(a[high_index]>a[median_index])
   {
     tmp_arr[tmp_index]=a[high_index];
     --high_index;
     --tmp_index;
   }
  else
   {
     tmp_arr[tmp_index]=a[median_index];
     --median_index;
     --tmp_index;
   }
 }

/* ho esaurito il primo o il secondo semiarray ? */
 while(high_index>=(middle_index+1))
  {
   tmp_arr[tmp_index]=a[high_index];
   --high_index;
   --tmp_index;
  }
 while(median_index>=low_index)
  {
   tmp_arr[tmp_index]=a[median_index];
   --tmp_index;
   --median_index;
  }

/* trasferisco il risultato dall'array temporaneo all mio array */
memcpy(&a[low_index], tmp_arr, numel*sizeof(int));
}

void scambia(int *a, int *b)
{
 int s;
 s=*a;
 *a=*b;
 *b=s;
}