bac informatique (cours.exercices.corrigé.devoirs...plus

Le tri par insertion


[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
Figure: Exemple de tri par insertion


Une méthode complètement différente est le tri par insertion.
C'est la méthode utilisée pour trier un paquet de cartes. On prend une
carte, puis 2 et on les met dans l'ordre si nécessaire, puis 3 et on
met la [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] carte à sa place dans les 2 premières, ... De manière générale on suppose les [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] premières cartes triées. On prend la [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] carte, et on essaie de la mettre à sa place dans les [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] cartes déjà triées. Et on continue jusqu'à [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]. Ceci donne le programme suivant

procedure TriInsertion;

var i, j, v: integer;

begin
for i := 2 to N do
begin
v := a; j := i;
while a[j-1] > v do
begin a[j] := a[j-1]; j:= j-1 end;
a[j] := v;
end;
end; Pour classer le [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] élément du tableau a, on regarde successivement en marche arrière à partir du [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة].
On décale les éléments visités vers la droite pour pouvoir mettre a[i]
à sa juste place. Le programme précédent contient une légère erreur, si
a[i] est le plus petit élément du tableau, car on va sortir du tableau
par la gauche. On peut toujours y remédier en supposant qu'on rajoute
un élément a[0] valant -maxint. On dit alors que l'on a mis une [i]sentinelle
à gauche du tableau a. Ceci n'est pas toujours possible, et il faudra
alors rajouter un test sur l'indice j dans la boucle while. Ainsi, pour
le tri par insertion, l'exemple numérique précédent est dans la figure
Le nombre de comparaisons pour insérer un élément dans la suite triée
de ceux qui le précédent est égal au nombre d'inversions qu'il présente
avec ceux-ci augmenté d'une unité. Soit [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] ce nombre de comparaisons. On a

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]

Pour la permutation [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] correspondant à la suite à trier, dont le nombre d'inversions est [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة], le nombre total de comparaisons pour le tri par insertion est

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]

D'où le nombre moyen de comparaisons

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]

Bien que l'ordre de grandeur soit toujours [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة],
ce tri est plus efficace que le tri par sélection. De plus, il a la
bonne propriété que le nombre d'opérations dépend fortement de l'ordre
initial du tableau. Dans le cas où le tableau est presque en ordre, il
y a peu d'inversions et très peu d'opérations sont nécessaires,
contrairement aux deux méthodes de tri précédentes. Le tri par
insertion est donc un bon tri si le tableau à trier a de bonnes chances
d'être presque ordonné.

Une variante du tri par insertion
est un tri dû à D. L. Shell en 1959, c'est une méthode de tri que l'on
peut sauter en première lecture. Son principe est d'éviter d'avoir à
faire de longues chaînes de déplacements si l'élément à insérer est
très petit. Nous laissons le lecteur fanatique en comprendre le sens,
et le mentionnons à titre anecdotique. Au lieu de comparer les éléments
adjacents pour l'insertion, on les compare tous les ..., 1093, 364,
121, 40, 13, 4, et 1 éléments. (On utilise la suite [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]).
Quand on finit par comparer des éléments consécutifs, ils ont de bonnes
chances d'être déjà dans l'ordre. On peut montrer que le tri Shell ne
fait pas plus que [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
comparaisons, et se comporte donc bien sur des fichiers de taille
raisonnable (5000 éléments). La démonstration est compliquée, et nous
la laissons en exercice difficile. On peut prendre tout autre
générateur que 3 pour générer les séquences à explorer. Pratt a montré
que pour des séquences de la forme [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة], le coût est [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] dans le pire cas (mais il est coûteux de mettre cette séquence des [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
dans l'ordre). Dans le cas général, le coût (dans le cas le pire) du
tri Shell est toujours un problème ouvert. Le tri Shell est très facile
à programmer et très efficace en pratique (c'est le tri utilisé dans le
noyau Maple).


procedure TriShell;
label 0;

var i, j, h, v: integer;

begin
h := 1; repeat h := 3*h + 1 until h > N;
repeat
h := h div 3;
for i := h + 1 to N do
begin
v := a[i]; j := i;
while a[j-h] > v do
begin
a[j] := a[j-h]; j := j - h;
if j <= h then goto 0;
end;
0:a[j] := v;
end
until h = 1;
end;

Principe 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). Imaginez un joueur de cartes qui dispose de cartes numérotées. Il a des cartes triées de la plus petite à la plus grande dans sa main gauche, et une carte dans la main droite. Où placer cette carte dans la main gauche de façon à ce qu'elle reste triée ? Il faut la placer après les cartes plus petites, et avant les cartes plus grandes. Par exemple, si la main gauche est (1 3 5 7), et que j'ai la carte 4 dans la main droite, il faut la placer après (1 3) et avant (5 7). Si l'on fait ça, on se retrouve avec la main gauche (1 3 4 5 7), qui est encore triée. Pour trier entièrement un ensemble de cartes dans le désordre, il suffit alors 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, donc elle bien 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ées) 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, triées, dans la main gauche : on a bien trié notre ensemble de cartes ommençons tout d’abord par l’opération d’insertion d’une carte de la main droite vers la main gauche. On veut placer la carte après toutes les cartes plus petites, et avant toutes les cartes plus grandes. Pour faire cela avec un tableau, on ne peut pas se contenter d’insérer simplement la carte : si on écrit la valeur de la carte dans une case, la valeur que cette case contenait avant est perdue. Il faut commencer par déplacer des cartes, pour laisser une case libre au bon endroit. Ici, il faut décaler d’une case vers la droite toutes les cartes plus grandes que la carte à insérer. Voici une ébauche de code (je donnerai la fonction complète ensuite) : Code : C1 2 for (j = taille_gauche; j > 0 && tab[j-1] >= element_a_inserer; j--) tab[j] = tab[j-1]; On part de la fin de la main gauche, tant que les cartes sont plus grandes que la carte à insérer, on les décale d’une case vers la droite. Le test j > 0 vérifie qu’on ne sort pas du tableau (ce qui pourrait arriver si toutes les cartes sont plus grandes que l’élément à insérer). La boucle s’arrête quand la carte tab[j-1] devient plus petite que l’élément à insérer. Il faut alors insérer cet élément juste après la case j-1, donc en j : Code : C1 2 3 4 5 6 7 void inserer(int element_a_inserer, int tab[], int taille_gauche) { int j; for (j = taille_gauche; j > 0 && tab[j-1] >= element_a_inserer; j--) tab[j] = tab[j-1]; tab[j] = element_a_inserer; ** Il y a une remarque importante à faire : taille_gauche est la taille de la main gauche, mais ce n’est pas la taille du tableau tab : comme on rajoute un élément, on a besoin que le tableau tab ait au moins une case de plus. On suppose donc que la taille de tab est toujours strictement supérieure à taille_gauche, et c’est pour cela qu’on s’autorise à écrire dans tab[taille_gauche] (au premier tour de boucle, quand j vaut taille_gauche). Quand on utilisera la fonction inserer, on vérifiera que la taille du tableau convient. Tri complet Il est maintenant très simple de coder le tri complet : Code : C1 2 3 4 5 6 void tri_insertion(int tab[], int taille) { int i; for(i = 1; i < taille; ++i) inserer(tab[i], tab, i); ** 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, tab[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 avant l’insertion à la main droite, et après à la main gauche. Au début de la boucle, [0...i-1] est la main gauche, puis on insère tab[i] avec la fonction vue au-dessus, donc la main gauche devient [0..i], et reste triée. En faisant varier i de 1 à taille-1 (i < taille est la condition d’arrêt), on insère donc peu à peu toutes les cartes 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 pour la main gauche soit toujours inférieure à 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <stdio.h> void tri_insertion(int tab[], int taille) { int i, j; for (i = 1; i < taille; ++i) { int elem = tab[i]; for (j = i; j > 0 && tab[j-1] >= elem; j--) tab[j] = tab[j-1]; tab[j] = elem; ** ** int main(void) { int i; int tableau[10] = {9, 8, 6, 7, 5, 2, 4, 1, 3, 0**; printf("avant le tri : "); for(i = 0; i < 10; i++) printf("%d ", tableau[i]); printf("\n"); tri_insertion(tableau, 10); printf("apres le tri : "); for(i = 0; i < 10; i++) printf("%d ", tableau[i]); printf("\n"); return 0; ** Complexité 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 saurais 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 variables dans les boucles 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 entre 0 et i fois : on part de la case i, et on va jusqu'à la case 0, en s'arrêtant avant si on trouve une carte plus petite que l'élément à insérer. On a donc un nombre de comparaisons variant entre 0 et i, donc 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 dans le pire cas Une bonne façon de mesurer la complexité de l'algorithme est de compter le nombre de calculs effectués "dans le pire cas", c'est à dire dans la configuration qui donnera le plus de travail possible à l'algorithme. Si on connaît bien ce cas, on a une idée du temps maximal que peut prendre l'algorithme (et donc on sait que "c'est toujours mieux que ...", ce qui est assez rassurant). Dans le pire cas, il faut décaler à chaque fois toutes les cartes de la main gauche, et pas seulement une partie d'entre elles. À chaque tour de boucle on a donc i comparaisons (la taille de la main gauche). 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 : Bash1 2 S = 1 + 2 + 3 + 4 + 5 + ... + N-5 + N-4 + N-3 + N-2 + N-1 S = N-1 + N-2 + N-3 + N-4 + N-5 +.... + 5 + 4 + 3 + 2 + 1 (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 : Bash1 2 3 S = 1 + 2 + 3 + 4 + 5 + ... + N-5 + N-4 + N-3 + N-2 + N-1 S = N-1 + N-2 + N-3 + N-4 + N-5 +.... + 5 + 4 + 3 + 2 + 1 2S = N + N + N + N + N + N + N + N + N + N + N 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 109 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.) Aller un peu plus loin J'ai dit que le pire cas possible était celui où chaque insertion décalait toutes les cartes de la main gauche. À quel genre de tableau en entrée cela correspond-il ? Si on doit décaler toutes les cartes, c'est que la carte qu'on veut insérer est plus petite que toutes les cartes de la main gauche : à chaque fois, la carte suivante est plus petite que toutes les autres. Cela correspond en fait à un tableau trié en ordre décroissant (du plus grand au plus petit), et donc exactement l'inverse que ce qu'on veut. Il paraît assez naturel que le pire cauchemar d'une fonction de tri en ordre croissant soit une entrée triée dans l'autre sens, mais en réalité ce n'est pas le pire cas de toutes les fonctions de tris, il y en a qui s'en sortent très bien. Remarque Il est possible de coder tri-insertion avec des listes chaînées (si vous ne savez pas ce que c'est, sautez ce paragraphe) au lieu de tableaux. L'avantage, c'est que c'est très simple d'insérer un élément au milieu d'une liste chaînée : il n'y a pas besoin de décaler toutes les valeurs suivantes. L'algorithme est donc considérablement simplifié (mais la complexité ne change pas). Cependant, en C, on ne dispose pas de listes chaînées par défaut, j'utilise donc les tableaux à la place..