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


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


  
	public static void main(String[] args) {

		int n = 5;
		Double[] 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));		
		
		Integer[] v = {7, 3, 5, 2, 4};
		mergeSort(v);
		System.out.println(Arrays.toString(v));
				
		Integer[] 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();
		Double[] da = new Double[l];
		
		for(int i=0;i<l;i++){
		   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 <T extends Comparable<T>> void selectionSort(T[] 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 <T> void scambia(T[] a, int i, int j) {
		numScambi ++;
		T 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 <T extends Comparable<T>> int trovaMinimo(T[] a, int i) {
		    System.out.println("metodo non implementato");
		    return -1;
	}	

	/**
	 * 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 <T extends Comparable<T>> void bubbleSort(T[] 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 <T extends Comparable<T>> void mergeSort(T[] 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 <T extends Comparable<T>> void msort(T[] a, int inf, int sup) {
		    System.out.println("metodo non implementato");
	}


	private static <T extends Comparable<T>> void merge(T[] a, int inf, int med, int sup) {		
		java.util.ArrayList<T> aux = new java.util.ArrayList<T>(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];
				aux.add(index,a[indexInf]);
				index++;
				indexInf++;
			} else {
				//aux[index] = a[indexSup];
				aux.add(index,a[indexSup]);  
				index++;
				indexSup++;				
			}
		}
		if (indexInf > med){
			for (int i = indexSup; i <= sup; i++) {
				//aux[index] = a[i];
				aux.add(index,a[i]);  
				index++;	
			}
		} else {
			for (int i = indexInf; i <= med; i++) {
				//aux[index] = a[i];  
				aux.add(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];
//		}
		for (int i = 0; i < aux.size(); i++) {
			  a[i+inf] = aux.get(i);
		}
//		numPassi+=aux.length;
		numPassi+=aux.size();
	}
	
	/**
	 * 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 <T extends Comparable<T>> void quickSort(T[] 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 <T extends Comparable<T>> void qSort(T[] a,int p,int r) {
		    System.out.println("metodo non implementato");
	}


	private static <T extends Comparable<T>> int partiziona(T[] a, int p, int r) {
		T x = a[r];
		System.out.println("pivot = "+x);
		
		int i = p-1;
		for (int j = p; 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+1, r);
		return i+1;
	}


	
}