Tri par création
Présentation
Autant le dire tout de suite, cet algorithme ne présente pas un grand intérêt au niveau algorithmique, il est relativement compliqué, pour un résultat pas franchement extraordinaire. Cependant, il est présenté ici à titre d’illustration et ne sera implémenté que dans le cas de tableaux. Cet algorithme peut être utilisé lorsque l’utilisateur souhaite conserver une copie du tableau original. Cependant, l’utilisateur aura sans doute un plus grand intérêt à faire une copie du tableau avant de le trier avec l’un des algorithmes les plus performants qui sont présentés à la suite.
Le principe de ce tri est de créer un tableau vide de même taille que le tableau à trier, puis de chercher dans le tableau à trier le plus petit élément afin de le placer en première position du tableau nouvellement créé. Ensuite, l’algorithme recherche successivement les éléments suivants afin de les placer, à la suite, dans le nouveau tableau. L’algorithme se termine lorsque tous les éléments du tableau ont été ajoutés.
Pour mettre en place ce tri, il faut écrire une fonction intermédiaire qui permet de chercher les différents éléments successifs. Cette fonction est appelée "pos_suivant".
Exemple
Soit le tableau à trier suivant :
| 5 | 3 | 1 | 2 | 6 | 4 |
Le nouveau tableau créé va évoluer ainsi au fil de l’algorithme :
| 1 | ? | ? | ? | ? | ? |
| 1 | 2 | ? | ? | ? | ? |
| 1 | 2 | 3 | ? | ? | ? |
| 1 | 2 | 3 | 4 | ? | ? |
| 1 | 2 | 3 | 4 | 5 | ? |
| 1 | 2 | 3 | 4 | 5 | 6 |
| Pseudo langage | |||||||
| C / C++ | Caml | Java | OCaml | ||||
Complexité
Pour mettre en œuvre cet algorithme, il y a un nombre fixe de comparaisons à effectuer. Considérons un tableau de n éléments. A chaque fois, pour trouver l’élément suivant le dernier élément trouvé, il faut parcourir tout le tableau. Soit, pour trouver les n éléments, parcourir n fois le tableau et, par voie de conséquence, effectuer n comparaisons. Ceci revient donc à effectuer n2 comparaisons. Dans la pratique, il faut constater que ce nombre est légèrement supérieur. Cela est du à quelques vérifications supplémentaires qui sont indispensables pour gérer quelques "effets de bords" comme la prise en charge des valeurs multiples. La complexité de l’algorithme est donc, de toute façon, en O(n2).
Accueil des algorithmes de tri
Article précédent : le tri bulle
Article suivant : le tri par sélection
