Algorithmes de tri

Un article collaboratif

Auteur

Thierry-Leriche-Dessirier

TODO

- Titre : Algorithmes de tri

- Auteur : Thierry-Leriche-Dessirier

- Parution : 22 novembre 2014

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2014 Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- 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

- I-F. Objets à trier

- I-G. Interfaces des algorithmes de tri

- II. Complexité

- III. Tests

- III-A. Cas simple

- III-B. Cas standards

- III-C. Distributions

- 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

- V. Conclusion

- V-A. Quand et comment utiliser tel ou tel tri ?

- V-B. Performances comparées

- V-C. Participez

- VI. Remerciements

- VII. Annexes

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 GitHub. Le projet se trouve à l'adresse https://github.com/thierryler/algo-tri-dvp et vous pouvez le récupérer depuis votre console Git à l'aide de la commande suivante :

Clone du projet Git

git clone https://github.com/thierryler/algo-tri-dvp.git

Le résultat devrait ressembler à la trace suivante :

Clone du projet Git

$ 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.0 dont vous trouverez une copie à 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.

Animal.java

public interface Animal {

String getName();

double getSize();

double getWeight();

int getAge();
}

AbstractAnimal.java

public abstract class AbstractAnimal implements Animal {

private String name;
private double size;
private double weight;
private int age;

...

Cat.java : DOES NOT implement Comparable

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.

Dog.java : DOES implement Comparable

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

Tri d'entiers

public interface IntSort {

void sort(final int[] tab);

}

Tri de comparables

public interface ComparableObjectSort {

<T extends Comparable<? super T>> void sort(final T[] tab);

<T extends Comparable<? super T>> void sort(final List<T> list);
}

Tri d'objets

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

AbstractIntSortTest.java

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

JavaIntSortTest.java

public class JavaIntSortTest extends AbstractIntSortTest {

public JavaIntSortTest() {
this.algo = new JavaIntSort();
}
}

JavaIntSort.java

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.

AbstractIntSortTest.java

@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.

AbstractIntSortTest.java

@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.

AbstractIntSortTest.java

@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.

AbstractIntSortTest.java

@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.

AbstractIntSortTest.java

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

VI - Remerciements

VII - Annexes