Le tri par insertion

L'algorithme principal du tri par insertion est un algorithme qui insère un élément dans une liste d'éléments déjà triés (par exemple, par ordre croissant).

Pour cela, il suffit de regarder dans l'ordre les éléments de la liste triée, jusqu'au moment ou l'élément que l'on doit insérer est plus petit que l'élément de la liste que l'on est en train de regarder. À ce moment-là, on insère l'élément à insérer, juste avant l'élément que l'on regardait.

Imaginez un joueur de cartes qui dispose de cartes numérotées. Il a une des cartes triées de la plus petite à la plus grande dans sa main gauche, et une carte dans la main droite. Il regarde les cartes de sa main gauche, de la plus grande à la plus petite, et à chaque fois, il compare la carte qu'il regarde et celle qui est dans sa main droite. Si la carte dans la main droite est plus petite, il l'insère juste avant la carte qu'il regardait dans sa main gauche.

Ainsi, la carte insérée est plus petite que la carte suivante (puisqu'on l'a justement insérée pour ça), et plus grande ou égale à la carte précédente (si elle avait été plus petite, elle aurait été insérée au tour d'avant).
L'ordre de la main gauche est conservé : elle est toujours triée.


Pour trier entièrement un ensemble de cartes, il suffit de placer toutes ses cartes dans la main droite (la main gauche est donc vide), et d'insérer les cartes une à une dans la main gauche, en suivant la procédure ci-dessus.

Au départ, la main gauche est vide : c'est donc une liste triée.
À chaque fois que l'on insère une carte depuis la main droite vers la main gauche, la main gauche reste triée, et la main droite (l'ensemble des cartes non triée) perd une carte. Ainsi, si la main droite comprenait au départ N cartes, en N insertions, on se retrouve avec O carte dans la main droite, et N cartes dans l'ordre dans la main gauche.

Commençons tout d'abord par l'opération d'insertion d'une carte de la main droite vers la main gauche.
Il faut que je donne en paramètre à la fonction qui effectue cette action la valeur d'une carte (la main droite), le tableau déjà trié (la main gauche), et la taille du tableau (pour faire la boucle for).

Je suppose que les éléments qui sont dans le tableau, donc que nous allons trier, sont des entiers (int ou long), mais vous pouvez adapter au type que vous voulez, du moment qu'il peut être comparé (l'opération '<' fonctionne).

Après avoir inséré l'élément de départ, il va falloir que je décale toutes les cartes suivantes vers la droite, et pour cela, les stocker dans une variable temporaire (entre le moment ou la carte précédente est placée à la place d'une carte, et le moment où cette dernière est insérée à la place de la carte suivante, je dois la conserver dans une variable temporaire). J'appelle element_a_inserer la variable qui contient la prochaine variable qui doit être insérée.
Au départ, elle contient l'élément que l'on veut insérer (logique ).

Quand est-ce qu'il faut insérer element_a_inserer ? Quand l'élément actuel est plus grand que l'élément à insérer. En effet, si l'on trie du plus petit au plus grand, si l'élément à insérer rencontre (au cours du parcours de la main gauche) un élément plus grand que lui, il doit impérativement être placé avant, donc à la place que l'élément occupait auparavant.
Il remplace donc l'élément rencontré, qui lui est stocké dans element_a_inserer, en attente d'être inséré plus loin.

Code : C

Quel rôle joue la 15^ème ligne ?
Il faut bien comprendre que la taille du tableau n'est pas forcément taille : je peux donner à la fonction un tableau de 5 entiers de long, et lui donner 3 comme taille. Ainsi, ma fonction ne regardera que les 3 premières cases du tableau, sans se soucier du reste.

À la fin, la fonction attribue une valeur à la case gauche[taille] du tableau. Cependant, dans un tableau classique, la dernière case est tab[taille-1] (M@teo explique pourquoi ici). Comment je fais alors, dans mon code, pour attribuer une valeur à gauche[taille] ? Cela ne devrait pas sortir du tableau ?

C'est là que l'astuce du taille passé en argument joue : en fait, pour avoir le droit d'assigner une valeur à gauche[taille] à la fin, il faut que la véritable taille de mon tableau soit au moins taille+1.

On ne pourra donc utiliser la fonction inserer_element que quand taille est plus petit que la taille inférieure du tableau. Vous verrez que dans le code final, cela ne pose aucun problème, mais il fallait tout de même préciser pourquoi on se permet une opération normalement interdite.

Voici le C final pour le tri par insertion.

Code : C

Je parcours le tableau avec l'indice i.

L'idée, c'est que je considère que toutes les cartes avant i sont triées, et que toutes les cartes après i ne sont pas triées, tableau[i] compris. i est donc la limite entre la main gauche et la main droite.
C'est pour cela d'ailleurs que la boucle commence à 1, et non à 0. La première carte, comme elle est toute seule, est déjà une liste triée, donc on peut l'inclure d'office dans la main gauche.

Comme i est la limite entre la main droite et la main gauche, la carte d'indice i appartient au début de la boucle à la main droite, et à la fin à la main gauche. Au début de la boucle, [0...i-1] est la main gauche, et [i..fin] la main droite, puis on insère tab[i] avec la fonction vue au dessus.

Comme cela, [0..i] est un tableau trié : la main gauche gagnait une case dans le tableau (on a rajouté une carte), et la main droite (qui est passée de [i..fin] à [i+1..fin]) a diminué d'une case (on lui a enlevé une carte pour l'insérer dans la main gauche).

En faisant varier i de 1 à taille-1 (i < taille est la condition d'arrêt), on insère peu à peu toutes les cartes de la main droite dans la main gauche.

Vous remarquerez que la taille donnée à la fonction inserer est i. Ainsi, comme la plus grande valeur de i possible est taille-1, la plus grande taille donnée à insérer est taille-1 aussi. J'avais dit qu'on ferait attention à ce que la taille donnée ne soit jamais la véritable taille du tableau, et vous pouvez maintenant le vérifier.


Voici une "version longue" (mais il n'y a pas de DVD bonus ) du code, qui réunit les deux fonctions en une seule, et un petit exemple d'utilisation :

Code : C

Comment peut-on évaluer la rapidité de cet algorithme ?
On pourrait mesurer son temps d'exécution sur mon ordinateur, mais cela n'est pas fiable parce que si on change d'ordinateur, le temps d'exécution change aussi : il peut être très rapide chez mon voisin (qui a un super PC) et très lent chez moi.
Une mesure plus rigoureuse de la "rapidité" de l'algorithme serait de mesurer le "nombre d'opérations" qu'il effectue : que ce soit chez moi ou chez mon voisin, pour trier le même tableau, il va effectuer le même nombre d'opérations, mais pas à la même vitesse.
L'avantage de ce critère est qu'il permet de comparer efficacement les algorithmes entre eux, indépendamment de l'ordinateur qui les exécute : si un algorithme fait plus d'opérations que le mien, il sera plus lent et chez moi, et chez mon voisin ; même si le nouvel algorithme est plus rapide chez mon voisin que l'algorithme actuel chez moi, je saurai qu'il est moins bon.

Il reste à définir ce qu'est une "opération". Plutôt que d'essayer de capturer absolument tous les détails du code (quand on incrémente une variable, quand on fait un test, etc.), on choisit une définition plus abstraite : on va dire que mon algorithme effectue une opération à chaque fois qu'il compare deux cartes entre elles.
C'est un choix assez pertinent, car la comparaison des cartes est le coeur de mon algorithme de tri. En particulier, si les éléments que l'on trie sont longs à comparer entre eux (ce qui est assez souvent le cas, quand on ne trie pas seulement des entiers, mais des structures plus complexes), ce sont effectivement les comparaisons qui prendront le plus de temps, et non pas les incrémentations de variable dans les boucle for, par exemple.

Il s'agit donc de calculer le nombre de comparaisons totales effectuées par le programme.

Supposons que N est la taille du tableau à trier. Je fais ici une approche globale et un calcul exact.
Si les maths vous ennuient, lisez juste l'approche.

Approche

Si N est la taille de l'entrée, le contenu de la première boucle est exécuté (l'ordinateur fait ce qui est dedans) environ N fois (plus précisément, N-1 fois).
À chaque fois qu'on exécute cette première boucle, on exécute la deuxième boucle i fois, c'est-à-dire un nombre de fois variant entre 0 et N.
Le nombre total d'exécutions de la deuxième est donc plus grand que N * 0, et plus petit que N * N, entre 0 et N².

On dit donc que le nombre de calculs de cet algorithme est de l'ordre de N² (dans le calcul détaillé, vous verrez que c'est plutôt N² / 2, mais que la différence n'a pas grand sens).

Calcul exact

L'algorithme parcourt le tableau de 1 à N (en donnant à l'indice en cours le nom i), et pendant ce parcours il fait i comparaisons à chaque fois.

Le nombre total de comparaisons est donc 1 + 2 + 3 + 4 + 5...+ N-1 (la dernière valeur de i est N-1).
Combien vaut ce nombre ? Appelons-le S. On a :
Code : Bash(J'ai renversé l'addition sur la deuxième ligne, ce qui ne change pas la valeur de S.)

En additionnant chaque somme des deux lignes "en colonnes", on additionne S + S, le résultat est 2S :
Code : Bash
On voit que 2S, c'est N ajouté à lui-même N-1 fois (de 1 à N-1, il y a N-1 termes).
On a donc 2S = N(N-1) ou S = N(N-1)/2.

Quand N est très grand, N(N-1) est approximativement égal à N², et le nombre de comparaisons de l'algorithme est donc d'environ N²/2, ou N²*0.5 comparaisons.

Cependant, le facteur 0.5 n'a pas grand sens : sur un ordinateur deux fois plus rapide, on ira deux fois plus vite et sur un ordinateur 2 fois plus lent, deux fois moins vite.
Pour estimer le temps mis par cet algorithme de manière indépendante de l'ordinateur, on dit donc que le nombre d'actions qu'il fait est "de l'ordre de N²".

Conclusion

En langage "scientifique", on dira que la complexité du tri par insertion est de O(N²).

En pratique, cela signifie que si l'on double la taille du tableau, l'algorithme sera 4 fois plus lent, et si on la multiplie par 10, 100 fois plus lent.

Approximation pratique

En une seconde, sur un processeur à 1 Ghz, en supposant qu'une comparaison (et les remplacements ou non qui l'accompagnent) prend 100 cycles de processeur (après une comparaison, je fais des manips de variables, etc. cela prend plusieurs cycles. 100 est une valeur crédible), en une seconde, on accomplit 10⁹ cycles, soit 10 millions de comparaisons.
La taille du tableau qui met une seconde à être trié sur un ordinateur à 1 Ghz est donc environ 3 000.
(3000 * 3000 est proche de 10 millions.)