import java.util.Arrays;
import java.util.Vector;
import java.util.Scanner;


public class SortAdv {
	private static int numPassi = 0;
	private static int numScambi = 0;

	public static void main(String[] args) {

		int n = 5;
		Comparable[] a = new Double[n];

		for (int i = 0; i < a.length; i++) { 
			a[i] = new Double(10.-i);;
		}
		
		System.out.println("inizializzo array con "+n+" elementi");
		System.out.println(Arrays.toString(a));
		
		selectionSort(a);
		
		System.out.println(Arrays.toString(a));		
		
		Comparable[] v = {7, 3, 5, 2, 4};
		mergeSort(v);
		System.out.println(Arrays.toString(v));
				
		Comparable[] z = {2, 8, 7, 1, 3, 5};
		System.out.println(Arrays.toString(z));				
		quickSort(z);
		System.out.println(Arrays.toString(z));
		
/*		Scanner sc = new Scanner(System.in);
		System.out.println("quanti double vuoi inserire ?");
		int l = sc.nextInt();
		Comparable[] da = new Double[l];
		
		for(int i=0;i<l;i++){
		  System.out.println("quanti double vuoi inserire ?");
		   da[i] = sc.nextDouble();
		}
		System.out.println(Arrays.toString(da));				
         	System.out.println("ordino");
		mergeSort(da);
		System.out.println(Arrays.toString(da));				
*/		
		
	}


	/**
	 * Ordina in maniera crescente il vettore di interi a utilizzando l'algoritmo Selection SortInteri.
	 * Il vettore a dopo l'esecuzione dell'algoritmo e' ordinato.
	 * 
	 * @param il vettore da ordinato
	 * */
	public static void selectionSort(Comparable[] a) {
		numPassi = 0;
		numScambi = 0;
		for (int i = 0; i < (a.length-1); i++) {
			int j = trovaMinimo(a,i);
			if (i!=j){
				scambia(a,i,j);
			}
			System.out.println(Arrays.toString(a));
		}
		System.out.println("array ordinato in "+numPassi+" passi con numero scambi = "+numScambi);		
	}

	/**
	 * Scambia gli elementi a[i] con a[j]
	 * 
	 *  @param a vettore
	 *  @param i primo indice 
	 *  @param j secondo indice
	 * */
	private static void scambia(Comparable[] a, int i, int j) {
		numScambi ++;
		Comparable aux = a[i];
		a[i] = a[j];
		a[j] = aux;
	}

	/**
	 * Trova l'indice dell'elemento minimo del vettore a 
	 * dall'elemento con indice i in poi.
	 * 
	 * @param a il vettore da ordinare
	 * @param i indice da cui partire per crcare il minimo 
	 * */
	private static int trovaMinimo(Comparable[] a, int i) {
		int minIndex = i;
		for (int j = i+1; j < a.length; j++) {
			numPassi++;
			if (a[minIndex].compareTo(a[j])>0){
				minIndex = j;
			}
		}
		return minIndex;
	}	

	
	/**
	 * Ordina in maniera crescente il vettore di interi a utilizzando l'algoritmo Bubble Sort.
	 * Il vettore a dopo l'esecuzione dell'algoritmo e' ordinato.
	 * 
	 * @param il vettore da ordinare
	 * */
	public static void bubbleSort(Comparable[] a) {
		  numPassi=0;
		  numScambi=0;
		  int n = a.length;
		  boolean ordinato = false;
		  for (int i = 0; i < n-1 && !ordinato; i++) {
			numPassi++;
		    ordinato = true;
		    for (int j = n-1; j > i; j--){
		        numPassi++;
		    	if (a[j-1].compareTo(a[j]) > 0) {
		    	 scambia(a, j-1, j);
		    	 ordinato = false;
		        }
		    }
			System.out.println(Arrays.toString(a));		    
		  }
		  System.out.println("array ordinato in "+numPassi+" passi con numero scambi = "+numScambi);		
		}

	/**
	 * Ordina in maniera crescente il vettore di interi a utilizzando l'algoritmo Merge Sort
	 * Il vettore a dopo l'esecuzione dell'algoritmo e' ordinato.
	 * 
	 * @param il vettore da ordinato
	 * */
	public static void mergeSort(Comparable[] a) {
		  numPassi=0;
		  numScambi=0;
		  msort(a,0,a.length-1);
		  System.out.println("Vettore ordinato in "+numPassi);
	}

	//procedura ricorsiva per algoritmo merge sort
	private static void msort(Comparable[] a, int inf, int sup) {
		if (inf<sup){
			int med = (inf + sup)/2;	
			System.out.println("split: "+UtilArray.toString(a, inf, med));
			System.out.println();
			System.out.println(UtilArray.toString(a, med+1, sup));
			System.out.println();
			msort(a, inf, med);
			msort(a, med+1, sup);
			merge(a,inf,med,sup);
			System.out.println("merge: "+UtilArray.toString(a, inf, sup));
			System.out.println();
		}
	}


	private static void merge(Comparable[] a, int inf, int med, int sup) {		
		Comparable[] aux = new Comparable[sup - inf + 1];
		int indexInf = inf;
		int indexSup = med+1;
		int index = 0;
		while ((indexInf<=med)&&(indexSup<=sup)){
			if (a[indexInf].compareTo(a[indexSup])<=0){
				aux[index] = a[indexInf];
				index++;
				indexInf++;
			} else {
				aux[index] = a[indexSup];
				index++;
				indexSup++;				
			}
		}
		if (indexInf > med){
			for (int i = indexSup; i <= sup; i++) {
				aux[index] = a[i];
				index++;	
			}
		} else {
			for (int i = indexInf; i <= med; i++) {
				aux[index] = a[i];
				index++;	
			}			
		}
		numPassi+=index;
		//copio vettore ausiliario in quello originale
		for (int i = 0; i < aux.length; i++) {
			a[i+inf] = aux[i];
		}
		numPassi+=aux.length;
	}
	
	/**
	 * Ordina il vettore a utilizzando l'algoritmo quicksort
	 * <p>
	 * richiama la funzione privata qSort per ordinare il vettore, inizializza numPassi e numScambi a 0 
	 * 
	 * @param a il vettore da ordinare
	 * */
	public static void quickSort(Comparable[] a){
		numPassi = 0;
		numScambi = 0;
		qSort(a, 0, a.length-1);
	}
	
	/**
	 * Ordina il vettore a dall'indice p all'indice r utilizzando l'algoritmo quicksort
	 * Sceglie come pivot l'ultimo elemento del vettore.
	 * 
	 * @param a il vettore da ordinare
	 * @param p indice iniziale
	 * @param r inidice finale
	 * */
	private static void qSort(Comparable[] a,int p,int r) {
		if (p<r){
			//partiziono array
			int q = partiziona(a,p,r);
			System.out.println("partizionato a "+UtilArray.toString(a,p,r)+", p = "+p+" r = "+r+" q = "+q);
			System.out.println("quicksort su "+UtilArray.toString(a, p, q-1));			
			
			qSort(a,p,q-1);
			System.out.println("quicksort su "+UtilArray.toString(a, q+1,r));			
			qSort(a,q+1,r);
		}
	}


	private static int partiziona(Comparable[] a, int p, int r) {
		Comparable x = a[p];
		System.out.println("pivot = "+x);
		
		int i = p;
		for (int j = p+1; j<=r; j++){
			if (a[j].compareTo(x) <= 0){
				i++;
				System.out.println("scambio a["+i+"] con a["+j+"]");
				scambia(a, i, j);
			}
		}
		scambia(a, i, p);
		return i;
	}

	
}