1 /////////////////////////////////////////////////////////////////7
   2 
   3 
   4 // ORDINAMENTO array
   5 // algoritmi di "bubble sort" e "merge sort"
   6 
   7 import java.util.Scanner;
   8 
   9 public class OrdinamentoArray {
  10 
  11 	public static Scanner input = new Scanner(System.in);
  12 
  13 	public static void leggiArray(int a[]){
  14 		System.out.println("Inserire " + a.length + " numeri interi, elementi di un array");
  15 		for (int i=0; i < a.length; i++)
  16 			a[i] = input.nextInt();
  17 	}
  18 	
  19 	public static void scriviArray(int a[]){
  20 		for (int i=0; i < a.length; i++)
  21 			System.out.print( a[i] + " " );
  22 		System.out.println();
  23 	}
  24 	
  25 	public static void copiaArray( int source[], int destination[]) {
  26 		for (int i = 0; i < source.length; i++)
  27 			destination[i] = source[i]; 
  28 	}
  29 	
  30 	public static void scambiaElementi (int v[], int i, int j) {
  31 		int temp = v[i];
  32 		v[i] = v[j];
  33 		v[j] = temp;
  34 	}
  35 
  36 	public static void bubbleSort ( int a[] ) {
  37 		boolean scambi = true;
  38 		int border = a.length - 1;
  39 		while ( scambi && border > 0 ) {
  40 			scambi = false;
  41 			for ( int j = 0; j < border; j++) {
  42 				if (a[j] < a[j+1]) {
  43 					scambiaElementi(a,j,j+1);
  44 					scambi = true;
  45 				}
  46 			}
  47 			border--;
  48 		}
  49 	}
  50 	
  51 	public static void mergeSort (int a[], int inf, int sup) {
  52 		if ( inf < sup ) {
  53 			int middle = ( inf + sup ) / 2;
  54 			mergeSort(a, inf, middle);
  55 			mergeSort(a, middle+1, sup);
  56 			merge(a, inf, middle, sup);
  57 		}
  58 	}
  59 	
  60 	public static void merge (int a[], int inf, int middle, int sup ) {
  61 		int temp [] = new int [a.length];
  62 		int i = inf;
  63 		int j = middle + 1;
  64 		int k = inf;
  65 		
  66 		while ( i <= middle && j <= sup) {
  67 			if (a[i] < a[j])
  68 				temp[k] = a[i++];
  69 			else 
  70 				temp[k] = a[j++];
  71 			k++;
  72 		}
  73 		
  74 		while ( i <= middle ) {
  75 			temp[k] = a[i];
  76 			i++;
  77 			k++;
  78 		}
  79 		
  80 		while ( j <= sup ) {
  81 			temp[k] = a[j];
  82 			j++;
  83 			k++;
  84 		}
  85 		
  86 		for (i = inf; i <= sup; i++)
  87 			a[i] = temp[i];
  88 	}
  89 
  90 	public static void main(String[] args) {
  91 
  92 		System.out.println(" Inserire un array di numeri interi.");
  93 		System.out.println(" Quanti elementi conterra' l'array? ");
  94 		
  95 		int v[] = new int[input.nextInt()];
  96 		leggiArray(v);
  97 		int v1[] = new int[v.length];
  98 		int v2[] = new int[v.length];
  99 		copiaArray(v,v1);
 100 		copiaArray(v,v2);
 101 
 102 		System.out.println(" L'array ordinato con l'algoritmo bubble sort e' il seguente.. ");
 103 		mergeSort(v1, 0, v1.length-1);
 104 		scriviArray(v1);
 105 		
 106 		System.out.println(" L'array ordinato con l'algoritmo merge sort (ricorsivo) e' il seguente.. ");
 107 		mergeSort(v2, 0, v2.length-1);
 108 		scriviArray(v2);
 109 	}
 110 
 111 }