1 // RICERCA in array
   2 // algoritmi di "ricerca lineare" e "ricerca binaria"
   3 
   4 
   5 import java.util.*;
   6 
   7 public class RicercaLineareBinaria {
   8 	
   9 	public static Scanner input = new Scanner(System.in);
  10 
  11 	public static void leggiArray(int a[]){
  12 		System.out.println("Inserire " + a.length + " numeri interi, elementi di un array");
  13 		for (int i=0; i < a.length; i++)
  14 			a[i] = input.nextInt();
  15 	}
  16 	
  17 	public static void scriviArray(int a[]){
  18 		for (int i=0; i < a.length; i++)
  19 			System.out.print( a[i] + " " );
  20 		System.out.println();
  21 	}
  22 	
  23 	public static int ricercaLineare ( int elem, int v[] ) {
  24 	    int nPassi = 0;
  25 	    boolean trovato = false;
  26 	    int i = 0;
  27 	    while(!trovato && i < v.length) {
  28 	        nPassi++;
  29 	        if(v[i] == elem) 
  30 	        	trovato = true;
  31 	        i++;
  32 	    }
  33 	    System.out.println("   --> numero di passi eseguiti dalla ricerca lineare: " + nPassi);
  34 	    if(trovato) 
  35 	    	return i-1;
  36 	    return -1;
  37 	}
  38 
  39 	public static int ricercaBinaria (int elem, int v[] ) {
  40 	    int nPassi = 0;
  41 	    int min = 0;
  42 	    int max = v.length-1;
  43 	    int mezzo = (max+min)/2;
  44 	    boolean trovato = false;
  45 	    while(!trovato && min <= max) {
  46 	        nPassi++;
  47 	        mezzo = (max+min)/2;
  48 	        if(v[mezzo] == elem) 
  49 	        	trovato=true; 
  50 	        if(v[mezzo] < elem) 
  51 	        	min = mezzo + 1;
  52 	        else max = mezzo - 1;
  53 	    }
  54 	    System.out.println("   --> numero di passi eseguiti dalla ricerca binaria: " + nPassi);
  55 	    if(trovato) 
  56 	    	return mezzo;
  57 	    return -1;
  58 	}
  59 	
  60 	public static int ricercaLineareRicorsiva (int elem, int v[], int pos) {  
  61 		if ( pos < 0)
  62 			return -1;
  63 		if ( elem == v[pos] )
  64 			return pos;
  65 		return ricercaLineareRicorsiva(elem, v, pos-1);
  66 	}
  67 
  68 	public static int ricercaBinariaRicorsiva (int elem, int v[], int inf, int sup) {
  69 		if( sup < inf )
  70 			return -1;
  71 	
  72 		int med = (inf + sup)/2;
  73 		if (elem == v[med])
  74 			return med;
  75 		if (elem < v[med])
  76 			return ricercaBinariaRicorsiva(elem, v, inf, med-1);
  77 		return ricercaBinariaRicorsiva(elem, v, med+1, sup);
  78 	}
  79 
  80 
  81 	public static void main(String[] args) {
  82 
  83 		System.out.println(" Inserire un array di numeri interi.");
  84 		System.out.println(" Quanti elementi conterra' l'array? ");
  85 		
  86 		int v[] = new int[input.nextInt()];
  87 		leggiArray(v);
  88 		
  89 		System.out.println(" Quale elemento si vuole ricercare nell'array? ");
  90 		
  91 		int elem = input.nextInt();
  92 		
  93 	    int posizione = ricercaLineare(elem,v);
  94 	    if (posizione >= 0)
  95 	    	System.out.println("Ricerca lineare: l'elemento " + elem + " si trova in posizione " + posizione);
  96 	    else
  97 	    	System.out.println("Ricerca lineare: l'elemento " + elem + " NON e' presente nell'array.");
  98 	    
  99 	    posizione = ricercaBinaria(elem,v);
 100 	    if (posizione >= 0)
 101 	    	System.out.println("Ricerca binaria: l'elemento " + elem + " si trova in posizione " + posizione);
 102 	    else
 103 	    	System.out.println("Ricerca binaria: l'elemento " + elem + " NON e' presente nell'array.");
 104 	    
 105 	    posizione = ricercaLineareRicorsiva(elem, v, v.length-1 );
 106 	    if (posizione >= 0)
 107 	    	System.out.println("Ricerca lineare ricorsiva: l'elemento " + elem + " si trova in posizione " + posizione);
 108 	    else
 109 	    	System.out.println("Ricerca lineare ricorsiva: l'elemento " + elem + " NON e' presente nell'array.");
 110 	    
 111 	    posizione = ricercaBinariaRicorsiva(elem, v, 0, v.length-1);
 112 	    if (posizione >= 0)
 113 	    	System.out.println("Ricerca binaria ricorsiva: l'elemento " + elem + " si trova in posizione " + posizione);
 114 	    else
 115 	    	System.out.println("Ricerca binaria ricorsiva: l'elemento " + elem + " NON e' presente nell'array.");
 116 	}
 117 
 118 }
 119 
 120 
 121 /////////////////////////////////////////////////////////////////7
 122 
 123 
 124 // ORDINAMENTO array
 125 // algoritmi di "bubble sort" e "merge sort"
 126 
 127 import java.util.Scanner;
 128 
 129 public class OrdinamentoArray {
 130 
 131 	public static Scanner input = new Scanner(System.in);
 132 
 133 	public static void leggiArray(int a[]){
 134 		System.out.println("Inserire " + a.length + " numeri interi, elementi di un array");
 135 		for (int i=0; i < a.length; i++)
 136 			a[i] = input.nextInt();
 137 	}
 138 	
 139 	public static void scriviArray(int a[]){
 140 		for (int i=0; i < a.length; i++)
 141 			System.out.print( a[i] + " " );
 142 		System.out.println();
 143 	}
 144 	
 145 	public static void copiaArray( int source[], int destination[]) {
 146 		for (int i = 0; i < source.length; i++)
 147 			destination[i] = source[i]; 
 148 	}
 149 	
 150 	public static void scambiaElementi (int v[], int i, int j) {
 151 		int temp = v[i];
 152 		v[i] = v[j];
 153 		v[j] = temp;
 154 	}
 155 
 156 	public static void bubbleSort ( int a[] ) {
 157 		boolean scambi = true;
 158 		int border = a.length - 1;
 159 		while ( scambi && border > 0 ) {
 160 			scambi = false;
 161 			for ( int j = 0; j < border; j++) {
 162 				if (a[j] < a[j+1]) {
 163 					scambiaElementi(a,j,j+1);
 164 					scambi = true;
 165 				}
 166 			}
 167 			border--;
 168 		}
 169 	}
 170 	
 171 	public static void mergeSort (int a[], int inf, int sup) {
 172 		if ( inf < sup ) {
 173 			int middle = ( inf + sup ) / 2;
 174 			mergeSort(a, inf, middle);
 175 			mergeSort(a, middle+1, sup);
 176 			merge(a, inf, middle, sup);
 177 		}
 178 	}
 179 	
 180 	public static void merge (int a[], int inf, int middle, int sup ) {
 181 		int temp [] = new int [a.length];
 182 		int i = inf;
 183 		int j = middle + 1;
 184 		int k = inf;
 185 		
 186 		while ( i <= middle && j <= sup) {
 187 			if (a[i] < a[j])
 188 				temp[k] = a[i++];
 189 			else 
 190 				temp[k] = a[j++];
 191 			k++;
 192 		}
 193 		
 194 		while ( i <= middle ) {
 195 			temp[k] = a[i];
 196 			i++;
 197 			k++;
 198 		}
 199 		
 200 		while ( j <= sup ) {
 201 			temp[k] = a[j];
 202 			j++;
 203 			k++;
 204 		}
 205 		
 206 		for (i = inf; i <= sup; i++)
 207 			a[i] = temp[i];
 208 	}
 209 
 210 	public static void main(String[] args) {
 211 
 212 		System.out.println(" Inserire un array di numeri interi.");
 213 		System.out.println(" Quanti elementi conterra' l'array? ");
 214 		
 215 		int v[] = new int[input.nextInt()];
 216 		leggiArray(v);
 217 		int v1[] = new int[v.length];
 218 		int v2[] = new int[v.length];
 219 		copiaArray(v,v1);
 220 		copiaArray(v,v2);
 221 
 222 		System.out.println(" L'array ordinato con l'algoritmo bubble sort e' il seguente.. ");
 223 		mergeSort(v1, 0, v1.length-1);
 224 		scriviArray(v1);
 225 		
 226 		System.out.println(" L'array ordinato con l'algoritmo merge sort (ricorsivo) e' il seguente.. ");
 227 		mergeSort(v2, 0, v2.length-1);
 228 		scriviArray(v2);
 229 	}
 230 
 231 }