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

/*provare a cambiare N e aumentarlo sempre di piu' */
#define N 500

int vettore[N];

void riempi(int [], unsigned long );
void visualizza(int [], unsigned long );
void scambia (int [], unsigned long , unsigned long);
void QSort (int [], long inf, long sup);
void BubbleSort(int [], unsigned long dim);

int main(void)
{

   time_t tstart,tend;

   printf("\nConfronto tra Bubble Sort e Quick Sort: Dimensione = %u \n",N);
   riempi(vettore,N);
/*   visualizza(vettore,N);*/
   printf("\nPremi un tasto per iniziare ad ordinare con BubbleSort");
   getchar();
   tstart = time(NULL);
   BubbleSort(vettore,N);
   tend = time(NULL);
/*   visualizza(vettore,N);*/
   printf("\nHo finito, ho impiegato %f secondi ",difftime(tend,tstart));
   printf("\nPremi un tasto per continuare ");
   getchar();

   riempi(vettore,N);
/*   visualizza(vettore,N);*/
   printf("\nPremi un tasto per iniziare ad ordinare con QuickSort");
   getchar();
   tstart = time(NULL);
   QSort(vettore,0,N-1);
   
   tend = time(NULL);
/*   visualizza(vettore,N);*/
   printf("\nHo finito, ho impiegato %f secondi ",difftime(tend,tstart));
   printf("\nPremi un tasto per finire il programma ");
   getchar();
}

void riempi(int v[], unsigned long dim){
   unsigned long i;

   for (i=0; i<dim; i++)
          v[i]=rand();
}

void visualizza(int v[], unsigned long dim){
   unsigned long i;

   for (i=0; i<dim; i++)
        printf("L'elemento di indice %u e' %d \n",i,v[i]);
}


void scambia (int v[], unsigned long i, unsigned long j)
{
  	int tmp=v[i];
   	v[i]=v[j];
   	v[j]=tmp;
}

void QSort (int v[], long inf, long sup)
{
	int pivot=v[(inf+sup)/2];
  long i=inf,j=sup;

  while (i<=j) {
		while (v[i]<pivot) i++;
		while (v[j]>pivot) j--;
		if (i<j)
			scambia(v,i,j);
		if (i<=j) {
			i++;
			j--;
  	}
	} 
	if (inf<j) QSort(v,inf,j);
	if (i<sup) QSort(v,i,sup);
}


void BubbleSort(int v[], unsigned long dim){
 unsigned long i,j;
 unsigned short ordinato=0;

 for (j=0;j<dim-1 && !ordinato;j++){
  ordinato=1;
  for (i=dim-1;i>j;i--)
     if (v[i]<v[i-1]){
             scambia(v,i,i-1);
             ordinato=0;
     }
 }
}