// allsort.java
//   from "Algorithms in Java, parts 1-4", 3rd ed, R. Sedgewick,
//    2003, Addison Wesley
//   some simplification by Prabhas Chongstitvatana   18 November 2009


// the first part is the skeleton of basic sort program
//   It is "all-in-one" file. Its sort routine is "insertion sort".

class ArraySortBasic {
    static int cnt = 0;
    static boolean less(double v, double w){
        cnt++; return v < w;
    }
    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){
        if( less(a[j], a[i]) )
            exch(a, i, j);
    }
    static void sort(double[] a, int l, int r){
        for(int i = l+1; i <= r; r++)
            for(int j = i; j > l; j--)
                compExch(a, j-1, j);
    }
    public static void main (String[] args){
        int N = Integer.parseInt(args[0]);
        double a[] = new double[N];
        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++)
                Out.println(a[i] + " ");
        Out.println("Compares used: " + cnt);
    }
}

// selection sort
//   first, find the smallest element, and exchange it with
//   the element in the first position.
//   Then, find the second smallest ...

static void selection(double[] a, int l, int r){
    for (int i = l; i < r; i++){
        int min = i;
        for (int j = i+1; j <= r; j++)
            if( less(a[j], a[min])
                min = j;
        exch(a, i, min);
    }
}


// bubble sort

static void bubble(double[] a, int l, int r){
    for (int i = l; i < r; i++)
        for (int j = r; j > i; j--)
            compExch(a, j-1, j);
}

// shell sort
//   increment sequence: 1 4 13 40 121 364 1093 9841 ...
//   in practice a good sequence gives at most 25% speed up
//   this sequence gives O(N^(3/2))

static void shell(double[] a, int l , int r){
    int h;
    for (h = 1; h <= (r-l)/9; h = 3*h+1);
    while ( h > 0 ){
        for (int i = l+h; i <= r; i++){
            int j = i;
            double v = a[i];
            while ( j >= l+h && less(v, a[j-h])){
                a[j] = a[j-h];
                j -= h;
            }
            a[j] = v;
        }
        h /= 3;
    }
}

// logarithmic notation
//   log N  (not specify base)
//   ln N   (base e = 2.71823...)
//   lg N   (base 2)

// quick sort
//    worst case  (N^2)/2 comparisons
//    average case  2N ln N comparisons

static void quicksort(double[] a, int l, int r){
    if (r <= l) return;
    int i = partition(a, l, r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
}

//  partitioning element v (arbitrary choose a[r])
//  left <= v, right >= v
//  l..i (left partition),  i..j (unprocess), j..r (right partition)

static int partition(double[] a, int l , int r){
    int i = l-1;
    int j = r;
    double v = a[r];
    for( ;; ){
        do{ i++; } while (less(a[i], v);
        do{ j--; } while (less(v,a[j]) && (j != l));
        if( i >= j) break;
        exch(a, i, j);
    }
    exch(a, i, r);
    return i;
}

// median-of-three partitioning
//  take sample from three elements, use the median of the three
//  sample left, middle, right

static void quicksort2(double[] a, int l, int r){
    if (r <= l) return;
    exch(a, (l+r)/2, r-1);
    compExch(a, l, r-1);
    compExch(a, l, r);
    compExch(a, r-1, r);
    int i = partition(a, l+1, r-1);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
}

// merge sort

static void mergesort(double[] a, int l, int r){
    if( r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);
    mergesort(a, m+1, r);
    merge(a, l, m, r);
}

static void merge(double[] c, int cl,
                  double[] a, int al, int ar,
                  double[] b, int bl, int br){
    int i = al;
    int j = bl;
    for (int k = cl; k < cl+ar-al+br-bl+1; k++){
        if ( i > ar ){
            c[k] = b[j];
            j++;
            continue;
        }
        if ( j > br ){
            c[k] = a[i];
            i++;
            continue;
        }
        if (less(a[i], b[j]){
            c[k] = a[i];
            i++;
        }else{
            c[k] = b[j];
            j++;
        }
    }
}


// radix sort
//   extract the ith digit from a key
//   MSD (most significant digit) radix sort  (left to right)
//   LSD (least significant digit) radix sort (right to left)

// MSD radix sort
//   generalise  partition into M bins
//   key with first byte 0: bin 0
//   key with first byte 1: bin 1
//   ....
//   key with first byte M-1: bin M-1

//   type myItem allows access to bytes of the keys
//      digit(a,d) gets digit d of myItem a
//      myItem.R  radix (length)

//   first pass, count the number of occurences of each leading digit value
//   these counts tell us where the partitions fall
//   second pass, use counts to move items to their positions in aux[]

static void radixMSD(myItem[] a, int l, int r, int d){
    int i, j;
    int cnt[] = new int[myItem.R+1];
    if ( r <= l ) return;
    for ( j = 0; j < myItem.R; j++ )
        cnt[j] = 0;
    for ( i = 1; i <= r; i++)
        cnt[digit(a[i], d) + 1]++;
    for ( j = 1; j <= myItem.R; j++)
        cnt[j] += cnt[j - 1];
    for ( i = l; i <= r; i++)
        aux[cnt[digit(a[i], d)]++ ] = a[i];
    for ( i = l; i <= r; i++)
        a[i] = aux[i-l];
    radixMSD(a, l, l+cnt[0]-1, d+1);
    for (j = 0; j < myItem.R-1; j++)
        radixMSD(a, l+cnt[j], l+cnt[j+1]-1, d+1);
}