// doing a bubble-sort

class BasicSort {
    static int cnt = 0;
    static int N = 20;
    static double a[] = new double[N];

    static void exch(double[] a, int i, int j){
        double t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    static void compExch(double[] a, int i, int j){
        cnt++;
        if( (a[j] < a[i]) )
            exch(a, i, j);
    }
/*
    // this version always runs to n^2
    static void sort(double[] a, int l, int r){
        for(int i = l; i < r; i++)
            for(int j = l; j < r; j++)
            compExch(a, j, j+1);
    }
*/
    // this version reduces r at each round
    static void sort(double[] a, int l, int r){
        for(int i = r; i > l; i--)
            for(int j = l; j < i; j++)
                compExch(a, j, j+1);
    }

    public static void main (String[] args){
        for(int i = 0; i < N; i++)
            a[i] = Math.random();
        sort(a, 0, N-1);
        if( N < 100 )
            for(int i = 0; i < N; i++)
                System.out.println(a[i] + " ");
        System.out.println("Compares used: " + cnt);
    }
}