/*
 * contiene due versioni dell'algoritmo BUBBLE SORT
 */

public class BubbleSort
{
	public static int[] randomVett(int dim, int maxVal)
	{
		int[] x=new int[dim];
		
		for(int i=0; i<dim; i++)
			x[i] = (int)(Math.random()*maxVal);

		return x;
	}


	public static void stampaVett(int[] vettore)
	{
		for(int i=0; i<vettore.length; i++)
		{
			System.out.println(vettore[i]);
		}
	}


	public static long ordinaConBubble(int[] valori)
/* restituisce il numero di millisecondi impiegati
 * altrimenti per ordinare un array sarebbe stato opportuno definire un metodo void
 */
 	{
// istante di inizio dell'ordinamento
		long inizio = System.currentTimeMillis(); 
		int fineSequenza = valori.length-1;
		do
		{
			for(int i=0; i<fineSequenza; i++)
			{
				if(valori[i] > valori[i+1])
				{
					int appoggio=valori[i];
					valori[i]=valori[i+1];
					valori[i+1]=appoggio;
				}
			}
			fineSequenza--;
		}
		while(fineSequenza > 0);
// istante di termine dell'ordinamento
		long fine = System.currentTimeMillis(); 
		return fine-inizio;
	}


	public static long ordinaConBubbleOttimizzato(int[] valori)
/* restituisce il numero di millisecondi impiegati
 * altrimenti per ordinare un array sarebbe stato opportuno definire un metodo void
 */
	{
// istante di inizio dell'ordinamento
		long inizio = System.currentTimeMillis(); 
		boolean ordinato;
		int fineSequenza = valori.length-1;
		do
		{
// la variabile e' true
			ordinato = true;
			for(int i=0; i<fineSequenza; i++)
			{
				if(valori[i] > valori[i+1])
				{
// se e' necessario almeno uno scambio la variabile diventa false
					ordinato = false;
					int appoggio=valori[i];
					valori[i]=valori[i+1];
					valori[i+1]=appoggio;
				}
			}
			fineSequenza--;
		}
		while(!ordinato); // il ciclo continua se in questa scansione e' stato necessario scambiare
// istante di termine dell'ordinamento
		long fine = System.currentTimeMillis(); 
		return fine-inizio;
	}


	public static void main(String[] args)
	// Ordina l'array con l'algoritmo a bolle
	{
		int n=50000;

		int[] v = randomVett(n,50000);
		System.out.println("Bubble: "+n+" elementi in "+ordinaConBubble(v)+ " millisecondi");
		
		v = randomVett(n,50000);
		System.out.println("BubbleOttimizzato: "+n+" elementi in "+ordinaConBubbleOttimizzato(v)+ " millisecondi");
		
		System.exit(0);
	}
}