import java.awt.*;
import java.util.Random;
import zuclib.*;
class Contatore
{
    public long confronti;
    public long assegnamenti;
    public Contatore()
    {
        confronti = 0;
        assegnamenti = 0;
    }
    public void reset()
    {
        confronti = 0;
        assegnamenti = 0;
    }
    public String toString()
    {
        return "Confronti : "+confronti+" Assegnamenti: "+assegnamenti;
    }
}
public class Test
{
    public static void bubble(int[] array,Contatore c)
    {
        c.reset();
        for(int i = 0; i < array.length; i++) {
            boolean flag = false;
            for(int j = 0; j < array.length-1; j++) {
                c.confronti++;
                if(array[j]>array[j+1]) {
                    c.assegnamenti+=3;
                    int k = array[j];
                    array[j] = array[j+1];
                    array[j+1] = k;
                    flag=true;
                }
            }
            if(!flag) break;
        }
    }
    public static void selection(int[] array,Contatore c)
    {
        c.reset();
        int posmin = 0;
        for(int i=0;i<array.length;i++)
        {
            int minimo = array[i];
            for(int k = i+1;k<array.length;k++)
            {
                c.confronti++;
                if(array[k]<minimo)
                {
                    c.assegnamenti+=2;
                    minimo = array[k];
                    posmin = k;
                }
            }
            c.assegnamenti+=3;
            int scambio = array[i];
            array[i] = minimo;
            array[posmin] = scambio;
        }
    }
    public static int[] caricaRand(int n,long seed)
    {
        int[] newarray = new int[n];
        Random r = new Random();
        if(seed!=0)
        {
            r.setSeed(seed);
        }
        for(int i=0;i<n;i++)
        {
            newarray[i] = r.nextInt(101);
        }
        return newarray;
    }
    public static int[] caricaSeq(int n,boolean reverse)
    {
        int[] newarray = new int[n];
        if(reverse)
        {
            for(int i=0;i<n;i++)
            {
                newarray[i] = n-i-1;
            }
        }else{
            for(int i=0;i<n;i++)
            {
                newarray[i] = i;
            }
        }

        return newarray;
    }
    public static void mostra(int[] array)
    {
        for(int i = 0;i<array.length;i++)
        {
            System.out.println(array[i]);
        }
    }
    public static double size = 600;
    public static double converti(double N)
    {
        return N/size;
    }
    public static void main(String[] args)
    {
        Tartaruga t = new Tartaruga();
        t.pennaSu();
        t.gotoXY(0,0);
        t.pennaGiu();
        t.setColore(Color.BLACK);
        Contatore c = new Contatore();
        int[] array;
        double startX = 0.1;
        for(int i = 10;i<=100000;i*=10)
        {
            array = caricaSeq(i/100,false);
            bubble(array,c);
            t.gotoXY(startX,0.000001*c.assegnamenti);
            startX+=0.1;
        }
    }
}