File Eserc3.java

import java.util.Random;
 
class ArrayContatore {
 
    private double[] a;
 
    private long tot;
 
    public ArrayContatore(int n) {
        a=new double[n];
        tot=0;
    }
 
    public void set(int i, double x) {
        tot++;
        a[i]=x;
    }
 
    public double get(int i) {
        tot++;
        return a[i];
    }
 
    public long getCounter() {
        return tot;
    }
 
    public void resetCounter() {
        tot=0;
    }
 
    public String toString() {
        String s=new String();
        int i;
        for(i=0; i<a.length; i++)
            if(i<a.length-1)
                s+=a[i]+", ";
            else
                s+=a[i];
        return s;
    }
 
}
 
 
public class Eserc3 {
 
    private static void scambia(ArrayContatore a, int i, int j) {
        double temp=a.get(i);
        a.set(i, a.get(j));
        a.set(j, temp);
    }
 
    private static long insertionSort(ArrayContatore a, int h, int f) {
        a.resetCounter();
        int i;
        for(i=h+1; i<=f; i++) {
            double curr=a.get(i);
            int j=i-1;
            while((j >= h) && (curr < a.get(j))) {
                a.set(j+1, a.get(j));
                j--;
            }
            a.set(j+1 , curr);
        }
        return a.getCounter();
    }
 
    private static long bubbleSort(ArrayContatore a, int h, int f) {
        a.resetCounter();
        int i, j;
        boolean scambio=true;
        while(scambio) {
            scambio=false;
            for(i=h; i<f; i++) {
                if(a.get(i+1) < a.get(i)) {
                    scambia(a, i, i+1);
                    scambio=true;
                }
            }
            f--;  //Ho già portato l'elemento più pesante in fondo all'array
        }
        return a.getCounter();
    }
 
    private static long mergeSortRic(ArrayContatore a, int i, int f) {
        if(f<=i) return 0;
        int m=(i+f)/2;
        long tot1=mergeSortRic(a, i, m);
        long tot2=mergeSortRic(a, m+1, f);
        int h=i; //Salvo i
        //Merge
        int j=m+1;
        ArrayContatore b=new ArrayContatore(f-i+1);
        int k=0;
        while(i<=m && j<=f) {
            if(a.get(i) < a.get(j)) {
                b.set(k, a.get(i));
                i++;
            } else {
                b.set(k, a.get(j));
                j++;
            }
            k++;
        }
        while(i<=m) {
            b.set(k, a.get(i));
            i++;
            k++;
        }
        while(j<=f) {
            b.set(k, a.get(j));
            j++;
            k++;
        }
        //Ricopio
        for(i=0; i<(f-h+1); i++)
            a.set(i+h, b.get(i));
        return tot1+tot2+b.getCounter();
    }
 
    private static long mergeSort(ArrayContatore a, int i, int f) {
        a.resetCounter();
        return mergeSortRic(a, i, f) + a.getCounter();
    }
 
    private static void quickSortRic(ArrayContatore a, int i, int j) {
        if(i<j) {
            int h=i;
            int k=j;
            int m=(i+j)/2;
            double p=a.get(m);
            scambia(a, m, j);
            j--;
            while(i<j) {
                while(i<j && a.get(i)<p)
                    i++;
                while(i<j && a.get(j)>=p)
                    j--;
                if(i<j)
                    scambia(a, i, j);
            }
            if(j==h) {
                //Se j è arrivato all'inizio dell'array,
                //significa che il minimo o è il pivot
                //oppure sta all'inizio dell'array
                if(a.get(h)>p)
                    scambia(a, j, k);
                //Ora il minimo è all'inizio dell'array
                quickSortRic(a, h+1, k);
            } else {
                //Altrimenti, abbiamo ridotto la dimensione dei
                //sottoproblemi e possiamo procedere con la ricorsione
                quickSortRic(a, h, j);
                quickSortRic(a, j, k);
            }
        }
    }
 
    private static long quickSort(ArrayContatore a, int i, int j) {
        a.resetCounter();
        quickSortRic(a, i, j);
        return a.getCounter();
    }
 
    private static ArrayContatore generaCrescente(int n) {
        ArrayContatore a=new ArrayContatore(n);
        int i=0;
        for(i=0; i<n; i++)
            a.set(i, i);
        a.resetCounter();
        return a;
    }
 
    private static ArrayContatore generaDecrescente(int n) {
        ArrayContatore a=new ArrayContatore(n);
        int i=0;
        for(i=0; i<n; i++)
            a.set(i, n-i);
        a.resetCounter();
        return a;
    }
 
    private static ArrayContatore generaRandom(int n, double a, double b) {
        ArrayContatore arr=new ArrayContatore(n);
        int i=0;
        Random r=new Random();
        for(i=0; i<n; i++)
            arr.set(i, a+r.nextDouble()*(b-a));
        arr.resetCounter();
        return arr;
    }
 
    public static void main(String[] args) {
        /*  Primo test: array generato "a mano"
                utile per il test degli algoritmi di ordinamento
 
            ArrayContatore a=new ArrayContatore(5);
            a.set(0, 5);
            a.set(1, 8);
            a.set(2, 3);
            a.set(3, 5);
            a.set(4, 3);
            System.out.println(a);
 
        */
 
        //Misure su array generati automaticamente
        int n=1000;
        ArrayContatore a=generaDecrescente(n);
        long tot=quickSort(a, 0, n-1);
        //System.out.println(a);
        System.out.println("Ha impiegato "+tot+" accessi");
    }
 
}