Exercice Java: Algorithme de tri par insertion, fusion et rapide (quicksort)

La classe abstraite Tri:

100

101

102

103

<span style="color: #333399;">abstract class Tri {
 
    /**
     * Stocke le nombre de comparaisons d'ordre sur les éléments du tableau
     */
    protected int nbrTests;
 
    /**
     * Stocke  le nombre de fois que l'algorithme utilise son opération élémentaire
     * ex: pour Quicksort l'opération élémentaire est la permutation (ou 'swap'
     * en anglais) de deux éléments du tableau
     */
    protected int nbrOps;
 
    /**
     * Ne sert qu'à l'affichage.
     * Ce tableau stocke les valeurs des éléments du tableau avant qu'ils ne soient triés.
     */
    protected int[] tableauEntree;
 
    /**
     * Le tableau sur lequel l'algorithme de tri travaille
     */
    protected int[] tableauTrie;
 
    /**
     * Champs d'information sur le tri utilisé.
     * Il peuvent être redéfinis dans les sous classes
     * Ex: nomTri = "quickSort"et nomOp = "swap"; dans le constructeur
     * de QuickSort
     */
    protected String nomTri = "tri quelconque";
    protected String nomOp = "operation quelconque";
 
    public void initialiser(int[] unTableau) {
        nbrTests = 0;
        nbrOps = 0;
        tableauEntree = new int[unTableau.length];
        tableauTrie = new int[unTableau.length];
        for (int i = 0; i < unTableau.length; i++) {
            tableauEntree[i] = unTableau[i];
            tableauTrie[i] = unTableau[i];
        }
    }
 
    /**
     * La méthode de tri propre à chaque sous-classe
     * sera définie dans la sous-classe.
     */
    public int trier() {
        nbrTests = 0;
        nbrOps = 0;
 
        algorithmeTri(0, tableauTrie.length - 1);
 
        return (nbrTests + nbrOps);
    }
 
    /**
     * algorithmeTri sera défini dans les sous classes
     */
    abstract void algorithmeTri(int indiceMin, int indiceMax);
 
    /**
     * Ici au lieu de définir une méthode affiche, on redéfinit la méthode
     * toString qui est appellée automatiquement quand on fait un print de
     * l'objet.
     * ex: System.out.println(new QuickSort(new double[] {1 2}))
     * va afficher le nombre d'opérations effectuées par QuickSort
     * pour trier le tableau {1, 2}
     */
    public String toString() {
        String marker = " *** ";
        String size = "" + tableauEntree.length;
        String input = "";
        for (int i = 0; i < tableauEntree.length; i++) {
            input = input + tableauEntree[i] + " ";
        }
 
        // ? est un opérateur ternaire permettant de
        // faire la même chose qu'un if-then-else:
        // (cond) ? siOui : siNon
        String stats = nbrTests + " test d'ordre " + ((nbrTests > 1) ? "s" : "") + " and " +
                nbrOps + " " + nomOp + ((nbrOps > 1) ? "s" : "");
 
        return marker + nomTri + ": " + input + "\n" + marker +
                "     ->    " + getSortedString(0, tableauTrie.length - 1) + "\n" +
                marker + "taille du tableau d'entrée: " + size + "\n" +
                marker + "a requis " + stats;
    }
 
    public String getSortedString(int inf, int sup) {
        String output = "";
        inf = ((inf < 0) ? 0 : inf);
        sup = ((sup >= tableauTrie.length) ? tableauTrie.length - 1 : sup);
        if (inf <= sup) {
            for (int i = inf; i <= sup; i++) {
                output = output + tableauTrie[i] + " ";
            }
        }
        return output;
    }
}</span>

La sous classe pour le tri par insertion

<span style="color: #333399;">/**
 * ***********************************************************
 * Tri par insertion
 * Classe fournissant l'algorithme de tri ainsi que les éléments
 * d'informations permettant de le tester empiriquement
 * ************************************************************
 */
class InsertionSort extends Tri {
 
    // Constructeur de l'objet tri par insertion
    public InsertionSort() {
        nomTri = "Tri par insertion";
        nomOp = "swap";
    }
 
    // Tri par insertion: si l'on part d'un tableau trié et qu'on lui ajoute un
    // élément à la bonne place on obtient de nouveau un tableau trié
    // On commence avec le premier élément comme tableau trié initial
    public void algorithmeTri(int g, int d) {
        int i, j;
        int temp;
        for (i = g + 1; i <= d; i++) {
            temp = tableauTrie[i];
            j = i - 1;
            while ((j >= 0) && (tableauTrie[j] > temp)) {
                tableauTrie[j + 1] = tableauTrie[j];
                nbrOp++;
                nbrTest++; // On compte les comparaisons et permutations
                j--;
            }
            tableauTrie[j + 1] = temp;
        }
    }
 
}</span>

La sous classe pour le tri par fusion:
L’algorithme implémenté ici part de l’hypothèse restrictive que les tableaux ont pour tailles des puissances de 2 (c-àd: 2ⁿ, n quelconque), ce qui corresponds au cas de fonctionnement optimal pour l’algorithme et aux données qui vous sont fournies dans les jeux de tests. Comme exercice complémentaire vous pourrez le généraliser.

<span style="color: #333399;">/**
 * ***********************************************************
 * Tri par fusion
 * classe fournissant l'algorithme de tri ainsi que les éléments
 * d'informations permettant de le tester empiriquement
 * ************************************************************
 */
class FusionSort extends Tri {
 
    /**
     * Tableau intermédiaire permettant de faire la fusion
     */
    private int[] temp;
 
    /**
     * Constructeur
     */
    public FusionSort() {
        nomTri = "Tri par fusion";
        nomOp = "assignation";
    }
 
    public int trier() {
        temp = new int[tableauEntree.length];
        return (super.trier());
    }
 
    /**
     * Algorithme de tri par fusion
     */
    void algorithmeTri(int g, int d) {
        int i, j, k;
        // On suppose un tableau de taille 2^n
        // g = borne gauche
        // d = borne droite
        // m = milieu (dernier élément de la partie gauche)
 
        // Condition d'arret de la récursion
        if (g < d) {
            int m = (g + d - 1) / 2;
            // La récursion
            algorithmeTri(g, m);
            algorithmeTri(m + 1, d);
 
            // On reclasse les éléments des deux tableaux dans l'ordre suivant :
            // tableau1 (du plus petit au plus grand) tableau2 (du plus grand au plus petit),
            // afin d'éviter de sortir des limites du tableau lors des assignations
            for (k = g; k <= m; k++) {
                temp[k] = tableauTrie[k];
            }
            for (k = m + 1; k <= d; k++) {
                temp[d + m + 1 - k] = tableauTrie[k];
            }
 
            i = g;
            j = d;
 
            // Fusion de deux tableaux trié en un
            for (k = g; k <= d; k++) {
                if (temp[i] < temp[j]) {
                    tableauTrie[k] = temp[i];
                    i++;
                    nbrTest++;
                    nbrOp++; // On compte le nb d'assignations et de comparaisons
                } else {
                    tableauTrie[k] = temp[j];
                    j--;
                    nbrTest++;
                    nbrOp++; // On compte le nb d'assignations et de comparaisons
                }
            }
        }
    }
}</span>

La sous classe pour le tri rapide:

<span style="color: #333399;">**
 * ***********************************************************
 * Tri rapide
 * Classe fournissant l'algorithme de tri ainsi que les éléments
 * d'informations permettant de le tester empiriquement
 * ************************************************************
 */
class QuickSort extends Tri {
    public QuickSort() {
        nomTri = "quickSort";
        nomOp = "swap";
    }
 
    public void algorithmeTri(int inf, int sup) {
        if (inf <= sup) {
 
            int i = inf + 1;
            int j = sup;
 
            // Séparation du tableau en deux sous-tableaux:
            // - l'un dont les éléments sont plus petits que l'élément pivot [inf]
            // - l'autre dont les éléments sont plus grands ou égaux à [inf]
            // L'indice de séparation est j:
            // [j] est plus grand que tout les éléments [i] tels que i<j
            // [j] est plus petit que tous les éléments [i] tels que i>j
            //
 
            while (j > i) {
                // La boucle s'arrête quand   j == i-1
                // ou j==i(quand [inf] est le plus grand élément du tableau)
 
                while (i < sup && tableauTrie[i] < tableauTrie[inf]) {
                    nbrTest++;
                    i++;
                }
                while (j > inf && tableauTrie[j] >= tableauTrie[inf]) {
                    nbrTest++;
                    j--;
                }
                if (i < j) {
                    swap(i, j);
                }
            }
 
            if (tableauTrie[inf] > tableauTrie[j]) {
                nbrTest++;
                swap(inf, j);
            }
            if (j - 1 > inf) {
                algorithmeTri(inf, j - 1);
            }
            if (j + 1 < sup) {
                algorithmeTri(j + 1, sup);
            }
        }
    }
 
    private void swap(int i, int j) {
        nbrOp++;
        int temp = tableauTrie[i];
        tableauTrie[i] = tableauTrie[j];
        tableauTrie[j] = temp;
 
    }
}</span>