import java.util.*;

/**
 * Démonstration des algorithmes de tri (ordre décroissant)
 *
 * Par rapport aux version croissantes, il suffit d'inverser les opérations de
 * comparaisons entre deux valeurs (lignes marquées par « xxx »).
 */
class TrisInverses {

    static final Random random = new Random();

    static void initTab(int[] tab, int max) {
        for (int i = 0; i < tab.length; i++)
            tab[i] = random.nextInt(max);
    }

    static void afficheTab(int[] tab) {
        System.out.print("[");
        for (int i = 0; i < tab.length; i++)
            System.out.print(" " + tab[i]);
        System.out.println(" ]");
    }

    static void triInsert(int[] tab) {
        int valeur;
        int limite;
        int place;
        for (limite = 1; limite < tab.length; limite++) {
            valeur = tab[limite];
            place = limite;
            while (place > 0 && tab[place - 1] < valeur) {      // xxx
                tab[place] = tab[place - 1];
                place = place - 1;
            }
            tab[place] = valeur;
        }
    }

    static void triSelect(int[] tab) {
        int iMin;
        int min;
        int limite;
        int i;
        for (limite = 0; limite < tab.length - 1; limite++) {
            iMin = limite;
            for (i = limite + 1; i < tab.length; i++) {
                if (tab[i] > tab[iMin])                         // xxx
                    iMin = i;
            }
            min = tab[iMin];
            tab[iMin] = tab[limite];
            tab[limite] = min;
        }
    }

    static void echangerValeurs(int[] tab, int i, int j) {
        int tmp = tab[i];
        tab[i] = tab[j];
        tab[j] = tmp;
    }

    static void triBulles(int[] tab) {
        int i;
        int limite;
        boolean echange;
        limite = 0;
        echange = true;
        while (echange && limite < tab.length - 1) {
            echange = false;
            for (i = tab.length - 1; i > limite; i--) {
                if (tab[i] > tab[i - 1]) {                      // xxx
                    echangerValeurs(tab, i, i - 1);
                    echange = true;
                }
            }
            limite = limite + 1;
        }
    }

    static void triBulles2(int[] tab) {
        int i;
        int limiteGauche;
        int limiteDroite;
        boolean echange;
        boolean sensDirect;     // direction du parcours
        limiteGauche = 0;
        limiteDroite = tab.length - 1;
        echange = true;
        sensDirect = true;
        while (echange && limiteGauche < limiteDroite) {
            echange = false;
            if (sensDirect) {
                // parcours normal: droite -> gauche
                for (i = limiteDroite; i > limiteGauche; i--) {
                    if (tab[i] > tab[i - 1]) {                  // xxx
                        echangerValeurs(tab, i, i - 1);
                        echange = true;
                    }
                }
                limiteGauche = limiteGauche + 1;
            } else {
                // parcours inverse : gauche -> droite
                for (i = limiteGauche; i < limiteDroite; i++) {
                    if (tab[i] < tab[i + 1]) {                  // xxx
                        echangerValeurs(tab, i, i + 1);
                        echange = true;
                    }
                }
                limiteDroite = limiteDroite - 1;
            }
            sensDirect = !sensDirect;
        }
    }

    public static void main(String[] args) {
        if (args.length != 2) {
            System.err.println("Usage: java TrisInverses taille algorithme");
            System.err.println("Algorithmes:\n" +
                               "  insert   tri par insertion\n" +
                               "  select   tri par sélection/permutation\n" +
                               "  bulles   tri à bulles\n" +
                               "  bulles2  double tri à bulles");
            System.exit(1);
        }

        int taille = Integer.parseInt(args[0]);
        String algo = args[1];

        int[] tab = new int[taille];
        initTab(tab, 10 * taille);

        System.out.println("Avant:");
        afficheTab(tab);

        String descr = "?";
        if (algo.equals("insert")) {
            descr = "tri par insertion";
            triInsert(tab);
        } else if (algo.equals("select")) {
            descr = "tri par sélection/permutation";
            triSelect(tab);
        } else if (algo.equals("bulles")) {
            descr = "tri à bulles";
            triBulles(tab);
        } else if (algo.equals("bulles2")) {
            descr = "double tri à bulles";
            triBulles2(tab);
        } else {
            System.err.println("Algorithme invalide : " + algo);
            System.exit(2);
        }

        System.out.println("Après " + descr + ":");
        afficheTab(tab);

    }
}