La classe abstraite Tri:
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;
}
}
La sous classe pour le tri par insertion
/**
* ***********************************************************
* 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;
}
}
}
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: 2n, 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.
/**
* ***********************************************************
* 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
}
}
}
}
}
La sous classe pour le tri rapide:
**
* ***********************************************************
* 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;
}
}
