import java.util.*;

/**
 * Démonstration des algorithmes de tri (chaînes de caractères)
 *
 * Par rapport aux versions sur les entiers, il faut changer les types des
 * éléments du tableau, et les opérations de comparaison.
 */
class TrisChaines {

    static final Random random = new Random();

    /**
     * Génère une chaîne de caractères aléatoire de longueur donnée.
     */
    static String randomString(int length) {
        StringBuilder sb = new StringBuilder(length);
        for (int i = 0; i < length; i++) {
            int family = random.nextInt(26 + 26 + 10);
            char c;
            if (family < 26)
                c = (char)('A' + random.nextInt(26));
            else if (family < 26 + 26)
                c = (char)('a' + random.nextInt(26));
            else
                c = (char)('0' + random.nextInt(10));
            sb.append(c);
        }
        return sb.toString();
    }

    static void initTab(String[] tab) {
        for (int i = 0; i < tab.length; i++)
            tab[i] = randomString(1 + random.nextInt(12));
    }

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

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

    static void triSelect(String[] tab) {
        int iMin;
        String 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].compareTo(tab[iMin]) < 0)
                    iMin = i;
            }
            min = tab[iMin];
            tab[iMin] = tab[limite];
            tab[limite] = min;
        }
    }

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

    static void triBulles(String[] 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].compareTo(tab[i - 1]) < 0) {
                    echangerValeurs(tab, i, i - 1);
                    echange = true;
                }
            }
            limite = limite + 1;
        }
    }

    static void triBulles2(String[] 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].compareTo(tab[i - 1]) < 0) {
                        echangerValeurs(tab, i, i - 1);
                        echange = true;
                    }
                }
                limiteGauche = limiteGauche + 1;
            } else {
                // parcours inverse : gauche -> droite
                for (i = limiteGauche; i < limiteDroite; i++) {
                    if (tab[i].compareTo(tab[i + 1]) > 0) {
                        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 TrisChaines 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];

        String[] tab = new String[taille];
        initTab(tab);

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

    }
}