Developpez.com

Plus de 2 000 forums
et jusqu'à 5 000 nouveaux messages par jour

Algorithmes de tri

Un article collaboratif

Thierry

TODO

Article lu   fois.

L'auteur

Profil ProSite personnelICAUDA

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

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 :

Clone du projet Git
Sélectionnez

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

Le résultat devrait ressembler à la trace suivante :

Clone du projet Git
Sélectionnez

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

Animal.java
Sélectionnez

public interface Animal {

	String getName();

	double getSize();

	double getWeight();

	int getAge();
}
AbstractAnimal.java
Sélectionnez

public abstract class AbstractAnimal implements Animal {

	private String name;
	private double size;
	private double weight;
	private int age;
	
	...
Cat.java : DOES NOT implement Comparable
Sélectionnez

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
Sélectionnez

public class Dog extends AbstractAnimal implements Animal, Comparable<Dog> {

	private DogRace race;
	
	@Override
	public int compareTo(Dog o) {
		...
	}
	
	...
Image non disponible

I-G. Interfaces des algorithmes de tri

TODO

Tri d'entiers
Sélectionnez

public interface IntSort {

	void sort(final int[] tab);

}
Tri de comparables
Sélectionnez

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
Sélectionnez

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
Sélectionnez

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
Sélectionnez

public class JavaIntSortTest extends AbstractIntSortTest {

	public JavaIntSortTest() {
		this.algo = new JavaIntSort();
	}
}
JavaIntSort.java
Sélectionnez

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
Sélectionnez

	@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
Sélectionnez

	@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
Sélectionnez
	
	@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
Sélectionnez
	
@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
Sélectionnez
	
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

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

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