I. Introduction▲
I-A. À propos▲
I-B. Versions des logiciels et bibliothèques utilisés▲
I-C. Mises à jour▲
I-D. Pourquoi on tri ? Pourquoi c'est important ?▲
I-E. Projet d'exemple▲
Puisque cet article et les éléments présentés sont placés sous le signe de la collaboration, un projet a été créé sur GitHubGitHub. Le projet se trouve à l'adresse https://github.com/thierryler/algo-tri-dvpProjet sur GitHub et vous pouvez le récupérer depuis votre console Git à l'aide de la commande suivante :
git clone https://github.com/thierryler/algo-tri-dvp.git
Le résultat devrait ressembler à la trace suivante :
$ git clone https://github.com/thierryler/algo-tri-dvp.git
Cloning into 'algo-tri-dvp'...
remote: Counting objects: 4, done.
remote: Compressing objects: 100% (4/4), done.
remote: Total 4 (delta 0), reused 0 (delta 0)
Unpacking objects: 100% (4/4), done.
Checking connectivity... done.
Le code est offert sous license Apache 2.0License Apache 2.0 dont vous trouverez une copieCopie de license Apache 2.0 à la racine du projet.
Pour des raisons de lisibilité, les codes des algorithmes sont présentés sans gestion d'exception. Reportez vous au projet GitHub et/ou aux annexes pour consulter les versions completes.
I-F. Objets à trier▲
En Java, on peut trier soit des primitifs (entiers, doubles, etc.) soit des objets. Pour illustrer le tri des objets, je vous propose d'utiliser la classe Cat, qui représente un chat et qui est un bean Java tout ce qu'il y a de plus classique.
public interface Animal {
String getName();
double getSize();
double getWeight();
int getAge();
}
public abstract class AbstractAnimal implements Animal {
private String name;
private double size;
private double weight;
private int age;
...
public class Cat extends AbstractAnimal implements Animal {
private CatRace race;
private String favoriteMilk;
...Je vous propose également d'utiliser la classe Dog, représentant un chien et qui, contrairement à Cat, implémente Comparable. Cette interface définit la méthode compareTo() et indique au JDK comment décider d'un chien est plus grand qu'un autre.
public class Dog extends AbstractAnimal implements Animal, Comparable<Dog> {
private DogRace race;
@Override
public int compareTo(Dog o) {
...
}
...
I-G. Interfaces des algorithmes de tri▲
TODO
public interface IntSort {
void sort(final int[] tab);
}
public interface ComparableObjectSort {
<T extends Comparable<? super T>> void sort(final T[] tab);
<T extends Comparable<? super T>> void sort(final List<T> list);
}
public interface ObjectSort {
<T> void sort(final Object[] tab, final Comparator<? super T> comparator);
<T> void sort(final List<T> list, final Comparator<? super T> comparator);
}Dans le code source du projet, sur GitHub, vous trouverez également des interfaces définissant des tris sur des copies des listes et des tableaux. Pour des raison de clareté, et sauf exception, les implémentations de ces versions ne seront pas présentées dans ce document.
II. Complexité▲
III. Tests▲
Avant de programmer des algorithmes de tri, je vous propose d'écrire quelques tests qui nous permettront de vérifier que tout fonctionne. Puisqu'on va s'intéresser à des listes assez grosses, les tests automatisés vont vite devenir indispensables.
Cette approche s'inscrit dans un démarche qualité. Pour cela, on va faire du TDD (Test Driven Development) et plus spécifiquement du 3T (Tests en Trois Temps) dont le premier temps, visant à écrire les contrats, a déjà été effectué durant l'introduction de ce document.
III-A. Cas simple▲
public abstract class AbstractIntSortTest {
protected IntSort algo;
@Test
public void testSimpleSort() {
// Arrange
final int[] tab = { 3, 0, 1, 7, 6, 9, 8, 2, 4, 5 };
final int size = tab.length;
// Act
algo.sort(tab);
// Assert
// On verifie qu'on n'a pas perdu des elements en chemin.
Assert.assertEquals(size, tab.length);
// On verifie que l'ordre des elements est le bon
int previous = Integer.MIN_VALUE;
for (final int elt : tab) {
Assert.assertTrue(previous <= elt);
previous = elt;
}
}
public class JavaIntSortTest extends AbstractIntSortTest {
public JavaIntSortTest() {
this.algo = new JavaIntSort();
}
}
public class JavaIntSort implements IntSort {
@Override
public void sort(int[] tab) {
throw new UnsupportedOperationException("Not yet");
}
}On pourrait penser que ça suffit mais il arrive, quand on a mal programmer l'algorithme, qu'on perde des valeurs. Je dois donc ajouter un test sur la taille.
@Test
public void testSimpleSort() {
// Arrange
final int[] tab = { 3, 0, 1, 7, 6, 9, 8, 2, 4, 5 };
final int size = tab.length;
// Act
algo.sort(tab);
// Assert
// On verifie qu'on n'a pas perdu des elements en chemin.
Assert.assertEquals(size, tab.length);
...
}Mais cela ne suffit toujours pas. En effet, durant l'écriture de cet article, il m'est aussi arrivé d'écraser des valeurs, sans toutefois changer le nombre d'éléments.
Une première solution consiste à dénombrer chaque valeur dans une map, avant et après. Il faut donc faire une sauvegarde du tableau avant.
@Test
public void testSimpleSort() {
// Arrange
final int[] tab = { 3, 0, 1, 7, 6, 9, 8, 2, 4, 5 };
final int size = tab.length;
final int[] backup = new int[size];
System.arraycopy(tab, 0, backup, 0, size);
// Act
algo.sort(tab);
// Assert
...
// On verifie qu'il a bien les meme elements avant et apres
final Map<Integer, Integer> mapBackup = tabToMap(backup);
final Map<Integer, Integer> mapTab = tabToMap(tab);
Assert.assertEquals(mapBackup, mapTab);
}
public static Map<Integer, Integer> tabToMap(final int[] tab) {
final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (final int elt : tab) {
int nb = 1;
if (map.containsKey(elt)) {
nb += (int) map.get(elt);
}
map.put(elt, nb);
}
return map;
}Ne criez pas tout de suite au scandale. Oui, vous avez raison ; cette solution est vraiment affreuse. J'ai cherché pendant longtemps comment faire mieux. Au final, je me suis dis qu'on pouvait bien se reposer sur les fonctions du JDK, qui ont déjà été testées par leurs auteurs.
@Test
public void testSimpleSort() {
// Arrange
final int[] tab = { 3, 0, 1, 7, 6, 9, 8, 2, 4, 5 };
final int size = tab.length;
final int[] expected = new int[size];
System.arraycopy(tab, 0, expected, 0, size);
Arrays.sort(expected);
// Act
algo.sort(tab);
// Assert
// On verifie juste que notre version triee est la meme que celle du JDK
Assert.assertArrayEquals(expected, tab);
}Dans cet article, j'ai donc finalement utilisé deux stratégies. Quand il y beaucoup de valeurs, j'utilise le tri du JDK pour comparer, comme ci-dessus. Et il y a très peu de valeurs, j'indique dirrectement le résultat attendu. Je trouve que c'est plus simple à lire.
@Test
public void testSimpleSort() {
// Arrange
final int[] tab = { 3, 0, 1, 7, 6, 9, 8, 2, 4, 5 };
final int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// Act
algo.sort(tab);
// Assert
// On verifie juste que notre version triee est la meme que celle du JDK
Assert.assertArrayEquals(expected, tab);
}Il ne reste plus qu'à factoriser un peu tout cela, car on va ajouter de nombreux tests dans la suite.
public abstract class AbstractIntSortTest {
protected IntSort algo;
@Test
public void testSimpleSort() {
// Arrange
final int[] tab = { 3, 0, 1, 7, 6, 9, 8, 2, 4, 5 };
final int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// Act
doTest(tab, expected);
}
@Test
public void testSimpleSortWithJdk() {
// Arrange
final int[] tab = { 3, 0, 1, 7, 6, 9, 8, 2, 4, 5 };
// Act and assert
doTestAndCompareWithJdk(tab);
}
private void doTestAndCompareWithJdk(final int[] tab) {
// Arrange
final int size = tab.length;
final int[] expected = new int[size];
System.arraycopy(tab, 0, expected, 0, size);
Arrays.sort(expected);
// Act and assert
doTest(tab, expected);
}
private void doTest(final int[] tab, final int[] expected) {
// Act
algo.sort(tab);
// Assert
// On verifie juste que notre version triee est la meme que celle du JDK
Assert.assertArrayEquals(expected, tab);
}III-B. Cas standards▲
TODO
III-C. Distributions▲
TODO
IV. Algorithmes▲
IV-A. Tri de Java▲
IV-B. Tri par selection▲
IV-C. Tri par insertion▲
IV-D. Tri rapide (Quick Sort)▲
IV-E. Tri fusion (Merge sort)▲
IV-F. Tri par inteclassement monotone▲
IV-G. Autres tris▲
Ce document est un article collaboratif. Vous pouvez donc proposer des algorithmes et des implémentations supplémentaires. Ils seront alors ajoutés à la suite.
V. Conclusion▲
TODO
V-A. Quand et comment utiliser tel ou tel tri ?▲
V-B. Performances comparées▲
V-C. Participez▲
TODO
Vos retours nous aident à améliorer nos publications. N'hésitez donc pas à commenter cet article sur le forum : TODO