/****
1) trovare un numero di elementi del vettore per cui
   la bubblesort() ci mette circa 10 secondi
   (circa ...... elementi)
2) codificare e controllare che funziona bubblesort2()
3) lanciare bubblesort2() con il numero di elementi
   nel vettore trovato al punto 1) e verificare se il 
   tempo e' minore o maggiore di 10 secondi
****/

/*** prova di Sorice:    100 mila elementi
     bubblesort() ----> circa 50 secondi
	 
	 bubblesort2()----> circa 30 secondi == piu' veloce di circa 40% 

     selectsort() ----> dovrebbe essere piu' veloce, limitando gli scambi a N-1
	                    circa fra 12 e 15 secondi per 100 mila elementi
						
	 
	 occorre una funzione richiamata N-1 volte, se N e' il numero di elementi
	 che ritorni la posizione dell'elemento minimo fra x e N con x
	 crescente (x==0 al primo giro, x == 1 secondo giro, ... x == N-2 ultimo giro
	 eccola: (vedi sotto pminimo() )

     insertsort() ----> occorre una funzione che, detta x la posizione
	                    in cui inserire un elemento, faccia il buco nel vettore
						in posizione x spostando gli y elementi a destra..
                        e' un po' difficile da scrivere...
	

	 void insertsort(int a[], int nelem)
	 {
	   int temp,i,j;
       for (i = 1; i < nelem; i++) 
	   {
         temp = a[i];
         j = i - 1;
         while (j >= 0 && a[j] > temp) 
		 {
            a[j + 1] = a[j];
            j--;
         }
         a[j + 1] = temp;
      }
     }	  
	
	 
     void selectsort(int v[], int nelem)
	 {
		int i,pm;
		for(i=0; i < nelem-1; i++)
		{
			pm=pminimo(v,i,nelem);
			scambia(v,i,pm);
		}
	 }
	 
	 int pminimo(int v[], int x, int nelem)
	 {
		int pm=x;   /// parto da v[x] e cerco il minimo
		int i;
		for (i=x; i <  nelem; i++)
			if (v[i] < v[pm])
				pm=i;
		return pm;
	 }
	 
	 
	 
	 
void bubblesort2(int v[], int nelem)
{
   int i,j;
   for(i=0; i < nelem-1; i++) // ciclo fino al penultimo
	for(j=i+1 ; j < nelem; j++) // ciclo interno
		if ( v[i] > v[j] )
			scambia(v,i,j); ///scambia i due elementi del vettore
	/// NON BASTA MAI UN UNICO CICLO per ordinare un vettore
}