// RICERCA in array
// algoritmi di "ricerca lineare" e "ricerca binaria"


import java.util.*;

public class RicercaLineareBinaria {
	
	public static Scanner input = new Scanner(System.in);

	public static void leggiArray(int a[]){
		System.out.println("Inserire " + a.length + " numeri interi, elementi di un array");
		for (int i=0; i < a.length; i++)
			a[i] = input.nextInt();
	}
	
	public static void scriviArray(int a[]){
		for (int i=0; i < a.length; i++)
			System.out.print( a[i] + " " );
		System.out.println();
	}
	
	public static int ricercaLineare ( int elem, int v[] ) {
	    int nPassi = 0;
	    boolean trovato = false;
	    int i = 0;
	    while(!trovato && i < v.length) {
	        nPassi++;
	        if(v[i] == elem) 
	        	trovato = true;
	        i++;
	    }
	    System.out.println("   --> numero di passi eseguiti dalla ricerca lineare: " + nPassi);
	    if(trovato) 
	    	return i-1;
	    return -1;
	}

	public static int ricercaBinaria (int elem, int v[] ) {
	    int nPassi = 0;
	    int min = 0;
	    int max = v.length-1;
	    int mezzo = (max+min)/2;
	    boolean trovato = false;
	    while(!trovato && min <= max) {
	        nPassi++;
	        mezzo = (max+min)/2;
	        if(v[mezzo] == elem) 
	        	trovato=true; 
	        if(v[mezzo] < elem) 
	        	min = mezzo + 1;
	        else max = mezzo - 1;
	    }
	    System.out.println("   --> numero di passi eseguiti dalla ricerca binaria: " + nPassi);
	    if(trovato) 
	    	return mezzo;
	    return -1;
	}
	
	public static int ricercaLineareRicorsiva (int elem, int v[], int pos) {  
		if ( pos < 0)
			return -1;
		if ( elem == v[pos] )
			return pos;
		return ricercaLineareRicorsiva(elem, v, pos-1);
	}

	public static int ricercaBinariaRicorsiva (int elem, int v[], int inf, int sup) {
		if( sup < inf )
			return -1;
	
		int med = (inf + sup)/2;
		if (elem == v[med])
			return med;
		if (elem < v[med])
			return ricercaBinariaRicorsiva(elem, v, inf, med-1);
		return ricercaBinariaRicorsiva(elem, v, med+1, sup);
	}


	public static void main(String[] args) {

		System.out.println(" Inserire un array di numeri interi.");
		System.out.println(" Quanti elementi conterra' l'array? ");
		
		int v[] = new int[input.nextInt()];
		leggiArray(v);
		
		System.out.println(" Quale elemento si vuole ricercare nell'array? ");
		
		int elem = input.nextInt();
		
	    int posizione = ricercaLineare(elem,v);
	    if (posizione >= 0)
	    	System.out.println("Ricerca lineare: l'elemento " + elem + " si trova in posizione " + posizione);
	    else
	    	System.out.println("Ricerca lineare: l'elemento " + elem + " NON e' presente nell'array.");
	    
	    posizione = ricercaBinaria(elem,v);
	    if (posizione >= 0)
	    	System.out.println("Ricerca binaria: l'elemento " + elem + " si trova in posizione " + posizione);
	    else
	    	System.out.println("Ricerca binaria: l'elemento " + elem + " NON e' presente nell'array.");
	    
	    posizione = ricercaLineareRicorsiva(elem, v, v.length-1 );
	    if (posizione >= 0)
	    	System.out.println("Ricerca lineare ricorsiva: l'elemento " + elem + " si trova in posizione " + posizione);
	    else
	    	System.out.println("Ricerca lineare ricorsiva: l'elemento " + elem + " NON e' presente nell'array.");
	    
	    posizione = ricercaBinariaRicorsiva(elem, v, 0, v.length-1);
	    if (posizione >= 0)
	    	System.out.println("Ricerca binaria ricorsiva: l'elemento " + elem + " si trova in posizione " + posizione);
	    else
	    	System.out.println("Ricerca binaria ricorsiva: l'elemento " + elem + " NON e' presente nell'array.");
	}

}


/////////////////////////////////////////////////////////////////7


// ORDINAMENTO array
// algoritmi di "bubble sort" e "merge sort"

import java.util.Scanner;

public class OrdinamentoArray {

	public static Scanner input = new Scanner(System.in);

	public static void leggiArray(int a[]){
		System.out.println("Inserire " + a.length + " numeri interi, elementi di un array");
		for (int i=0; i < a.length; i++)
			a[i] = input.nextInt();
	}
	
	public static void scriviArray(int a[]){
		for (int i=0; i < a.length; i++)
			System.out.print( a[i] + " " );
		System.out.println();
	}
	
	public static void copiaArray( int source[], int destination[]) {
		for (int i = 0; i < source.length; i++)
			destination[i] = source[i]; 
	}
	
	public static void scambiaElementi (int v[], int i, int j) {
		int temp = v[i];
		v[i] = v[j];
		v[j] = temp;
	}

	public static void bubbleSort ( int a[] ) {
		boolean scambi = true;
		int border = a.length - 1;
		while ( scambi && border > 0 ) {
			scambi = false;
			for ( int j = 0; j < border; j++) {
				if (a[j] < a[j+1]) {
					scambiaElementi(a,j,j+1);
					scambi = true;
				}
			}
			border--;
		}
	}
	
	public static void mergeSort (int a[], int inf, int sup) {
		if ( inf < sup ) {
			int middle = ( inf + sup ) / 2;
			mergeSort(a, inf, middle);
			mergeSort(a, middle+1, sup);
			merge(a, inf, middle, sup);
		}
	}
	
	public static void merge (int a[], int inf, int middle, int sup ) {
		int temp [] = new int [a.length];
		int i = inf;
		int j = middle + 1;
		int k = inf;
		
		while ( i <= middle && j <= sup) {
			if (a[i] < a[j])
				temp[k] = a[i++];
			else 
				temp[k] = a[j++];
			k++;
		}
		
		while ( i <= middle ) {
			temp[k] = a[i];
			i++;
			k++;
		}
		
		while ( j <= sup ) {
			temp[k] = a[j];
			j++;
			k++;
		}
		
		for (i = inf; i <= sup; i++)
			a[i] = temp[i];
	}

	public static void main(String[] args) {

		System.out.println(" Inserire un array di numeri interi.");
		System.out.println(" Quanti elementi conterra' l'array? ");
		
		int v[] = new int[input.nextInt()];
		leggiArray(v);
		int v1[] = new int[v.length];
		int v2[] = new int[v.length];
		copiaArray(v,v1);
		copiaArray(v,v2);

		System.out.println(" L'array ordinato con l'algoritmo bubble sort e' il seguente.. ");
		mergeSort(v1, 0, v1.length-1);
		scriviArray(v1);
		
		System.out.println(" L'array ordinato con l'algoritmo merge sort (ricorsivo) e' il seguente.. ");
		mergeSort(v2, 0, v2.length-1);
		scriviArray(v2);
	}

}