Discussion :

[mattj]

Q: Qu'est-ce qu'un algorithme de tri "stable"?

R:

Un algorithme de tri stable est un algorithme de tri conservant l'ordre initial de deux éléments égaux.

Exemple : si l'on trie par ordre croissant du nombre de lettres la liste de mots suivante :

{ 'abcd' , 'jo' , 'matt' , 'azerty' }

à l'aide d'un tri stable, on obtient la liste:

{ 'jo' , 'abcd' , 'matt' , 'azerty'}

[mattj]

Q: Qu'est-ce qu'un tri "sur place" (ou "en place")?

R:

Un tri est dit "sur place" s'il est effectué directement dans la structure de donnée initiale, et ne nécessite pas l'allocation d'une nouvelle structure.

Exemple : tri par insertion
Contre-Exemple : tri par fusion

[PRomu@ld]

Un tri est dit "sur place" s'il est effectué directement dans la structure de donnée initiale, et ne nécessite pas l'allocation d'une nouvelle structure.

En fait, on peu peut-être préciser, en disant que l'espace supplémentaire nécessaire à l'algorithme n'est pas fonction de la taille des entrées. Pour un algorithme de tri par comparaison (hormis les opérations spéciales sur les entiers), l'espace supplémentaire nécessaire n'est que l'espace d'un élément (pour effectuer l'echange des élements.)

Contre-Exemple : tri par fusion

Si tu veux mon avis, ton contre exemple n'est pas forcément judicieux, une certaine implémentation de l'algorithme peut se faire sur place. Le mieux comme contre exemple est de prendre un tri postal par exemple.

[PRomu@ld]

Je pense que ceci est plus à même d'être intégré dans la page source algorithmes.

http://algo.developpez.com/sources/