// LajitteluEsim.java SJ

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

class LajitteluEsim {

    public static void main(String[] args) {

        // ensimmäinen komentoriviparametri: alkioiden määrä
        int N = 10;
        if (args.length > 0)
            N = Integer.valueOf(args[0]);

        // toinen parametri: tulostetaanko vai ei, >1 = tulosta
        boolean tulosta = false;
        if (args.length > 1 && (Integer.valueOf(args[1]) > 0))
            tulosta = true;

        // kolmas parametri: järjesteyksessä vai ei
        // -1 : laskeva järjestys, 1 = kasvava järjestys, 0 = satunnainen
        int J = 0;
        if (args.length > 2)
            J = Integer.valueOf(args[2]);



        Integer[] taulu;
        long start;

        if (N <= 10000) {
            // Kuplalajittelu
            taulu = satunnainenTaulu(N, J, 1);
            if (tulosta)
                for (int i = 0; i < N; i++)
                    System.out.print(taulu[i] + " ");
            System.out.println();
            System.out.println("Kuplalajittelu alkaa");
            start = (new Date()).getTime();
            bubbleSort(taulu);
            System.out.println("               " +
                               ((new Date()).getTime()-start) + " ms");
            if (tulosta)
                for (int i = 0; i < N; i++)
                    System.out.print(taulu[i] + " ");
            System.out.println();
        }

        // Pikalajittelu
        taulu = satunnainenTaulu(N, J, 1);
        System.out.println("Pikalajittelu  alkaa");
        start = (new Date()).getTime();
        quicksort(taulu, 0, N-1);
        System.out.println("               " +
                           ((new Date()).getTime()-start) + " ms");
        if (tulosta)
            for (int i = 0; i < N; i++)
                System.out.print(taulu[i] + " ");
        System.out.println();

    } // main() 

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

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

        return taulu;
    } // satunnainenTaulu()


    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) {

        // jakoalkioksi ensimmäinen
        // NÄIN SAA TEHDÄ VAIN OPETUSTARKOITUKSESSA, EI KOSKAAN
        // OIKEASSA OHJELMASSA
        // Harjoitustehtävänä 3-mediaani
        E jakoalkio = A[i];

        // toistetaan kunnes i ja j törmäävät
        while (i < j) {

            // etsitään lopusta jakoalkiota pienempi
            while ((i < j) && (jakoalkio.compareTo(A[j]) < 0))
                j--;
            A[i] = A[j];

            // etsitään alusta jakoalkiota suurempi tai yhtäsuuri
            while ((i < j) && (jakoalkio.compareTo(A[i]) >= 0))
                i++;
            A[j] = A[i];

        } // while

        // jakoalkio paikalleen ja palautetaan sijainti
        A[i] = jakoalkio;
        return i;

    } // partition()



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

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


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

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

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

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

    } // countsort()



} // class LajitteluEsim