File Eserc6.java

import java.util.Random;
 
public class Eserc6 {
 
  public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
 
  public static void insertionSort(int[] arr) {
    int i=1, n=arr.length;
    while(i<n) {
      if(arr[i] < arr[i-1]) {
        int j = i-1;
        int tmp = arr[i];
        while(j >= 0 && arr[j] > tmp) {
          arr[j+1] = arr[j];
          j--;
        }
        arr[j+1] = tmp;
      }
      i++;
    }
  }
 
  public static void mergeSort(int[] arr, int i, int f) {
    if(f <= i)
      return;
    int m = (i+f)/2;
    mergeSort(arr, i, m);
    mergeSort(arr, m+1, f);
    //Merge step
    int[] tmp = new int[f-i+1];
    int i1 = i, i2 = m+1, j = 0;
    while(i1 <= m || i2 <= f)
      if(i2 > f || (i1 <=m && arr[i1] <= arr[i2]))
        tmp[j++] = arr[i1++];
      else
        tmp[j++] = arr[i2++];
    //Copy back to original array
    j = 0;
    while(i <= f)
      arr[i++] = tmp[j++];
  }
 
  public static void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length-1);
  }
 
  public static int[] generaArrayConScambi(int n, int s) {
    int[] arr = new int[n];
    for(int i=0; i<n; i++)
      arr[i] = i+1;
    Random r = new Random();
    for(int i=0; i<s; i++)
      swap(arr, r.nextInt(n), r.nextInt(n));
    return arr;
  }
 
  public static int[] generaArrayRandom(int n) {
    int[] arr = new int[n];
    Random r = new Random();
    for(int i=0; i<n; i++)
      arr[i] = r.nextInt();
    return arr;
  }
 
  public static boolean sortTest(int[] arr) {
    for(int i=0; i<arr.length-1; i++)
      if(arr[i] > arr[i+1])
        return false;
    return true;    
  }
 
  public static String arrayToString(int[] arr) {
    String s = "{";
    for(int i=0; i<arr.length - 1; i++)
      s += arr[i] + ", ";
    s += arr[arr.length-1] + "}";
    return s;
  }
 
  public static double runMergeSort(int[] arr, int k) {
    long time = System.currentTimeMillis();
    for(int i=0; i<k; i++) {
      int[] brr = arr.clone();
      mergeSort(brr);
    }
    return (double)(System.currentTimeMillis() - time)/k;
  }
 
  public static double runInsertionSort(int[] arr, int k) {
    long time = System.currentTimeMillis();
    for(int i=0; i<k; i++) {
      int[] brr = arr.clone();
      insertionSort(brr);
    }
    return (double)(System.currentTimeMillis() - time)/k;
  }
 
  public static void main(String[] args) {
 
    int n = 1000;
    int k = 1000;
    //Numero di esecuzioni di insertion sort su array casuale;
    //in generale lo scegliamo molto più piccolo di k perche' l'algoritmo e'
    //molto piu' lento!
    int k1 = 20;
 
    for(int s=40; s<=140; s+=10) {
      int[] a = generaArrayConScambi(n, s);
      System.out.println("s = " + s);
      System.out.println(runMergeSort(a, k));
      System.out.println(runInsertionSort(a, k));
      System.out.println();
    }
 
    int[] arr = generaArrayRandom(n);
    System.out.println("Random");
    System.out.println(runMergeSort(arr, k));
    System.out.println(runInsertionSort(arr, k1)); 
    System.out.println();
 
  }
 
}