// SortingExample.java SJ

import java.util.Date;
import java.util.Random;

class SortingExample {

    public static void main(String[] args) {

        // 1st argument: # of elements
        int N = 10;
        if (args.length > 0)
            N = Integer.valueOf(args[0]);

        // 2nd argument: print or not >1 = print
        boolean tulosta = false;
        if (args.length > 1 && (Integer.valueOf(args[1]) > 0))
            tulosta = true;

        // 3rd argument: order of input
        // -1 : decreasing, 1 = increasing, 0 = random
        int J = 0;
        if (args.length > 2)
            J = Integer.valueOf(args[2]);



        Integer[] array;
        long start;

        if (N <= 10000) {
            // Bubble sort
            array = randomArray(N, J, 1);
            if (tulosta)
                for (int i = 0; i < N; i++)
                    System.out.print(array[i] + " ");
            System.out.println();
            System.out.println("Bubblesort starts");
            start = (new Date()).getTime();
            bubbleSort(array);
            System.out.println("               " +
                               ((new Date()).getTime()-start) + " ms");
            if (tulosta)
                for (int i = 0; i < N; i++)
                    System.out.print(array[i] + " ");
            System.out.println();
        }

        // Pikasort
        array = randomArray(N, J, 1);
        System.out.println("Quicksort  starts");
        start = (new Date()).getTime();
        quicksort(array, 0, N-1);
        System.out.println("               " +
                           ((new Date()).getTime()-start) + " ms");
        if (tulosta)
            for (int i = 0; i < N; i++)
                System.out.print(array[i] + " ");
        System.out.println();

    } // main() 

    public static Integer[] randomArray(int N, int J, int seed) {
        Integer[] array = new Integer[N];

        Random r = new Random(seed);
        for (int i = 0; i < N; i++) {
            if (J == 0)
                array[i] = new Integer(r.nextInt(N*2));
            else if (J > 0)
                array[i] = new Integer(i);
            else
                array[i] = new Integer(N-i);
        }

        return array;
    } // randomArray()


    public static <E extends Comparable<? super E>>
                        void bubbleSort(E[] A) {
        for (int i = 0; i < A.length-1; i++) {
            for (int j = A.length-1; j > i; j--) {
                if (A[j-1].compareTo(A[j]) > 0) {
                    E tmp = A[j-1];
                    A[j-1] = A[j];
                    A[j] = tmp;
                }
            }
        }
    } // bubbleSort()



    public static <E extends Comparable<? super E>>
                    void quicksort(E[] A, int i, int j) {
        if (i < j) {
            int k = partition(A, i, j);
            quicksort(A, i, k-1);
            quicksort(A, k+1, j);
        }
    } // quicksort()

    public static <E extends Comparable<? super E>>
                    int partition(E[] A, int i, int j) {

        // first element as pivot
        // NEVER USE THIS IN REAL PROGRAM, JUST FOR
        // SIMPLEST POSSIBLE EDUCATIONAL VERSION
        // Better solution in exercises
        E pivot = A[i];

        // repeat until i and j collide
        while (i < j) {

            // find from end an element that is smaller than pivot
            while ((i < j) && (pivot.compareTo(A[j]) < 0))
                j--;
            A[i] = A[j];

            // find from start an element that is larger than pivot
            while ((i < j) && (pivot.compareTo(A[i]) >= 0))
                i++;
            A[j] = A[i];

        } // while

        // pivot to correct position, and return position
        A[i] = pivot;
        return i;

    } // partition()



    public static void mergesort(Comparable A[], int start, int end) {
        if (start < end) {
            int k = (start + end) / 2;
            mergesort(A, start, k);
            mergesort(A, k+1, end);
            merge(A, start, k, end);
        }
    } // mergesort()

    public static void merge(Comparable A[], int i, int k, int j) {
        // Exercise
    }


    public static void countsort(Integer A[], int max) {
        int[] occurrences = new int[max+1];

        for (int i = 0; i <= max; i++)
            occurrences[i] = 0;

        for (int i = 0; i < A.length; i++)
            occurrences[A[i]]++;

        int n = 0;
        for (int i = 0; i <= max; i++)
            for (int j = 0; j < occurrences[i]; j++)
                A[n++] = i;

    } // countsort()


} // class SortingExample