Version imprimable
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'}
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
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.)Citation:
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.
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.Citation:
Contre-Exemple : tri par fusion
Je pense que ceci est plus à même d'être intégré dans la page source algorithmes.
http://algo.developpez.com/sources/