1 of 247

Tri par insertion

Première NSI > Chapitre 10.

2 of 247

Algorithme de tri : définition

3 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

4 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8]

On part d’un tableau non-trié.

5 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8] >>>

Le tableau est maintenant stocké en mémoire.


0	1	2	3	4	5
27	5	9	18	11	8

tab

6 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8] >>> tri(tab)

On peut ensuite lui appliquer une fonction de tri.


0	1	2	3	4	5
27	5	9	18	11	8

tab

7 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8] >>> tri(tab) >>>

Le tableau est maintenant trié dans l’ordre croissant !


0	1	2	3	4	5
5	8	9	11	18	27

tab

8 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8] >>> tri(tab) >>>

Remarque. Le prompt est réapparu directement sans affichage de résultat renvoyé.


0	1	2	3	4	5
5	8	9	11	18	27

tab

9 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8] >>> tri(tab) >>>

Cela veut dire que la fonction tri ne renvoie rien : c’est bien une fonction mutateur.

Remarque. Le prompt est réapparu directement sans affichage de résultat renvoyé.


0	1	2	3	4	5
5	8	9	11	18	27

tab

10 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8] >>> tri(tab) >>>


0	1	2	3	4	5
5	8	9	11	18	27

tab

11 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8] >>> tri(tab) >>> tab

On peut maintenant interroger le contenu mémoire associé à tab.


0	1	2	3	4	5
5	8	9	11	18	27

tab

12 of 247

Définition. Un algorithme de tri :

prend en paramètre un tableau indexé tab ;
ne renvoie rien mais trie les éléments de tab dans l’ordre croissant.

Remarque. Un tel algorithme qui modifie une structure de données stockée en mémoire comme un tableau sans renvoyer d’information particulière est appelé “mutateur”.

Exemple.

>>> tab = [27, 5, 9, 18, 11, 8] >>> tri(tab) >>> tab [5, 8, 9, 11, 18, 27] >>>


0	1	2	3	4	5
5	8	9	11	18	27

tab

On a confirmation que le tableau est bien trié.

13 of 247

Algorithme de tri par insertion

14 of 247

Sommaire. Tri par insertion

Principe
Implémentation en Python
Complexité

15 of 247

Préambule

Pour découvrir par vous-même le principe du tri par insertion, cliquer sur les liens ci-dessous pour accéder à deux animations. Observer les animations avec attention.

16 of 247

Sommaire. Tri par insertion

Principe

algorithme simplifié
algorithme détaillé

Implémentation en Python
Complexité

17 of 247

Sommaire. Tri par insertion

Principe

algorithme simplifié
algorithme détaillé

Implémentation en Python
Complexité

18 of 247


							⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10
	⭡
	cle

Pour comprendre, prenons l'algorithme en cours sur un exemple de tableau.

19 of 247


							⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10
	⭡
	cle

La zone déjà triée apparaît en rouge.

20 of 247


							⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10
	⭡
	cle

À cette étape, on doit insérer 21 dans la zone déjà triée.

21 of 247

							21

	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94		70
	⭡
	10
	⭡
	cle

À quelle position doit-on insérer 21 ?

22 of 247

							21

	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94		70

	10
	⭡
	cle

Ces éléments sont tous plus grands que 21.

23 of 247

							21

	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94		70

	10
	⭡
	cle

On peut donc les décaler vers la droite.

24 of 247

			21

	0	1	2	3	4	5	6	7
tab	10	15		22	32	92	94	70

	10
	⭡
	cle

La position d’insertion apparaît alors.

25 of 247



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	70

	10
	⭡
	cle

La position d’insertion apparaît alors.

26 of 247



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	70

	10
	⭡
	cle

La zone déjà triée a augmenté d’une case.

27 of 247


			⬇
	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70
	⭡
	10
	⭡
	cle

Pour comprendre, prenons l'algorithme en cours sur le même tableau mais à une autre étape.

28 of 247


			⬇
	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70
	⭡
	10
	⭡
	cle

La zone déjà triée apparaît en rouge.

29 of 247


			⬇
	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70
	⭡
	10
	⭡
	cle

À cette étape, on doit insérer 15 dans la zone déjà triée.

30 of 247

À quelle position doit-on insérer 15 ?

			15

	0	1	2	3	4	5	6	7
tab	22	92		32	10	94	21	70

	10
	⭡
	cle

31 of 247

			15

	0	1	2	3	4	5	6	7
tab	22	92		32	10	94	21	70

	10
	⭡
	cle

Tous les éléments avant 15 sont tous plus grands que lui.

32 of 247

			15

	0	1	2	3	4	5	6	7
tab	22	92		32	10	94	21	70

	10
	⭡
	cle

On peut donc les décaler vers la droite.

33 of 247

	15

	0	1	2	3	4	5	6	7
tab		22	92	32	10	94	21	70

	10
	⭡
	cle

La position d’insertion apparaît alors dans ce cas en début de tableau.

34 of 247



	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

	10
	⭡
	cle

La position d’insertion apparaît alors dans ce cas en début de tableau.

35 of 247



	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

	10
	⭡
	cle

zone déjà triée a augmenté d’une case.

36 of 247

Observons maintenant l’algorithme en entier.



	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

	10
	⭡
	cle

37 of 247

Observons maintenant l’algorithme en entier.


	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

	10
	⭡
	cle

38 of 247


	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

	10
	⭡
	cle

Le 1er élément n’étant pas déplaçable à gauche, on ne

fait rien.

39 of 247


		⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

	10
	⭡
	cle

40 of 247

		22

	0	1	2	3	4	5	6	7
tab	92		15	32	10	94	21	70

	10
	⭡
	cle

41 of 247

		22

	0	1	2	3	4	5	6	7
tab	92		15	32	10	94	21	70

	10
	⭡
	cle

42 of 247

	22

	0	1	2	3	4	5	6	7
tab		92	15	32	10	94	21	70

	10
	⭡
	cle

43 of 247



	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70

	10
	⭡
	cle

44 of 247


			⬇
	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70

	10
	⭡
	cle

45 of 247

			15

	0	1	2	3	4	5	6	7
tab	22	92		32	10	94	21	70

	10
	⭡
	cle

46 of 247

			15

	0	1	2	3	4	5	6	7
tab	22	92		32	10	94	21	70

	10
	⭡
	cle

47 of 247

	15

	0	1	2	3	4	5	6	7
tab		22	92	32	10	94	21	70

	10
	⭡
	cle

48 of 247



	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

	10
	⭡
	cle

49 of 247


				⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

	10
	⭡
	cle

50 of 247

				32

	0	1	2	3	4	5	6	7
tab	15	22	92		10	94	21	70

	10
	⭡
	cle

51 of 247

				32

	0	1	2	3	4	5	6	7
tab	15	22	92		10	94	21	70

	10
	⭡
	cle

52 of 247

			32

	0	1	2	3	4	5	6	7
tab	15	22		92	10	94	21	70

	10
	⭡
	cle

53 of 247



	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

	10
	⭡
	cle

54 of 247


					⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

	10
	⭡
	cle

55 of 247

					10

	0	1	2	3	4	5	6	7
tab	15	22	32	92		94	21	70

	10
	⭡
	cle

56 of 247

					10

	0	1	2	3	4	5	6	7
tab	15	22	32	92		94	21	70

	10
	⭡
	cle

57 of 247

	10

	0	1	2	3	4	5	6	7
tab		15	22	32	92	94	21	70

	10
	⭡
	cle

58 of 247



	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70

	10
	⭡
	cle

59 of 247


						⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70

	10
	⭡
	cle

60 of 247


						⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70

	10
	⭡
	cle

Déjà bien placé !

61 of 247


							⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70

	10
	⭡
	cle

62 of 247

							21

	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94		70
	⭡
	10
	⭡
	cle

63 of 247

							21

	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94		70

	10
	⭡
	cle

64 of 247

			21

	0	1	2	3	4	5	6	7
tab	10	15		22	32	92	94	70

	10
	⭡
	cle

65 of 247



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	70

	10
	⭡
	cle

66 of 247


								⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	70

	10
	⭡
	cle

67 of 247

								70

	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94

	10
	⭡
	cle

68 of 247

								70

	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94

	10
	⭡
	cle

69 of 247

						70

	0	1	2	3	4	5	6	7
tab	10	15	21	22	32		92	94

	10
	⭡
	cle

70 of 247



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94

	10
	⭡
	cle

71 of 247



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94

	10
	⭡
	cle

72 of 247

Exercice.

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

								4

								5

								6

								7

10	11	15	17	18	19	23	25

73 of 247

Exercice. (Correction)

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

15	17	19	23	11	25	18	10	4

11	15	17	19	23	25	18	10	5

11	15	17	19	23	25	18	10	6

								7

10	11	15	17	18	19	23	25

74 of 247

Exercice. (Correction)

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

15	17	19	23	11	25	18	10	4

11	15	17	19	23	25	18	10	5

11	15	17	19	23	25	18	10	6

11	15	17	18	19	23	25	10	7

10	11	15	17	18	19	23	25

75 of 247

Sommaire. Tri par insertion

Principe

algorithme simplifié
algorithme détaillé

Implémentation en Python
Complexité

76 of 247



	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

Algorithme du tri par insertion

On part d’un tableau non-trié.

77 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

	i
	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

78 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

	i
	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

79 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.

	i
	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

	92
	⭡
	cle

80 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	i
	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

	92
	⭡
	cle

81 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

Comme on est au début du tableau, il n’y a pas d’éléments précédents !

	j	i
	⬇	⬇
	-1	0	1	2	3	4	5	6	7
tab		92	22	15	32	10	94	21	70

		92
		⭡
		cle

82 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

On ne fait donc rien et on passe à l’étape suivante !

		i
		⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

83 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

		i
		⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

		22
		⭡
		cle

84 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j	i
	⬇	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

		22
		⭡
		cle

92 est le 1er élément précédent à décaler.

85 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j	i
	⬇	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

		22
		⭡
		cle

92 est plus grand que la clé donc on le décale en faisant une copie à droite.

86 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j	i
	⬇	⬇
	0	1	2	3	4	5	6	7
tab	92	92	15	32	10	94	21	70

		22
		⭡
		cle

92 est plus grand que la clé donc on le décale en faisant une copie à droite.

87 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j	i
	⬇	⬇
	0	1	2	3	4	5	6	7
tab	92	92	15	32	10	94	21	70

		22
		⭡
		cle

Noter que le 22 a été perdu. Heureusement 22 a été mémorisé dans la clé !

88 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j	i
	⬇	⬇
	0	1	2	3	4	5	6	7
tab	92	92	15	32	10	94	21	70

		22
		⭡
		cle

Maintenant

92 est en double !

89 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j	i
	⬇	⬇
	0	1	2	3	4	5	6	7
tab	92	92	15	32	10	94	21	70

		22
		⭡
		cle

Maintenant que 92 a été copié à droite, son occurrence initiale est devenue inutile.

90 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j		i
	⬇		⬇
	-1	0	1	2	3	4	5	6	7
tab		92	92	15	32	10	94	21	70

			22
			⭡
			cle

Cette case est donc libérée pour une insertion !

91 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j		i
	⬇		⬇
	-1	0	1	2	3	4	5	6	7
tab		92	92	15	32	10	94	21	70

			22
			⭡
			cle

Comme on est au début du tableau, il n’y a plus d’éléments précédents !

92 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.

	j		i
	⬇		⬇
	-1	0	1	2	3	4	5	6	7
tab		92	92	15	32	10	94	21	70

			22
			⭡
			cle

On arrête donc les décalages à cette étape : on a trouvé la position d’insertion !

93 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	-1	0	1	2	3	4	5	6	7
tab		92	92	15	32	10	94	21	70
		⭡
		22
		⭡
		cle

On peut maintenant insérer la clé dans la case libérée !

94 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	-1	0	1	2	3	4	5	6	7
tab		22	92	15	32	10	94	21	70
		⭡
		22
		⭡
		cle

On peut maintenant insérer la clé dans la case libérée !

95 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	-1	0	1	2	3	4	5	6	7
tab		22	92	15	32	10	94	21	70

		22
		⭡
		cle

À la fin de l’étape, le tableau a retrouvé l’ensemble des éléments qu’il contenait au départ.

96 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	-1	0	1	2	3	4	5	6	7
tab		22	92	15	32	10	94	21	70

		22
		⭡
		cle

Passons à l’étape suivante !

97 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

			i
			⬇
	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70

Passons à l’étape suivante !

98 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

			i
			⬇
	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70

			15
			⭡
			cle

99 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j	i
		⬇	⬇
	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70

			15
			⭡
			cle

92 est le 1er élément précédent à décaler.

100 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j	i
		⬇	⬇
	0	1	2	3	4	5	6	7
tab	22	92	15	32	10	94	21	70

			15
			⭡
			cle

92 est plus grand que la clé donc on le décale en faisant une copie à droite.

101 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	0	1	2	3	4	5	6	7
tab	22	92	92	32	10	94	21	70

			15
			⭡
			cle

92 est plus grand que la clé donc on le décale en faisant une copie à droite.

102 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	0	1	2	3	4	5	6	7
tab	22	92	92	32	10	94	21	70

		15
		⭡
		cle

Faut-il insérer la clé ici ?

103 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	0	1	2	3	4	5	6	7
tab	22	92	92	32	10	94	21	70

		15
		⭡
		cle

Non car 15 serait mal placé !

104 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	0	1	2	3	4	5	6	7
tab	22	92	92	32	10	94	21	70

		15
		⭡
		cle

En effet, il reste un élément précédent plus grand que 15.

105 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	0	1	2	3	4	5	6	7
tab	22	92	92	32	10	94	21	70

		15
		⭡
		cle

On fait donc un décalage supplémentaire.

106 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j		i
	⬇		⬇
	0	1	2	3	4	5	6	7
tab	22	92	92	32	10	94	21	70

		15
		⭡
		cle

On fait donc un décalage supplémentaire.

107 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		22	22	92	32	10	94	21	70

			15
			⭡
			cle

On fait donc un décalage supplémentaire.

108 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		22	22	92	32	10	94	21	70

			15
			⭡
			cle

Comme on est au début du tableau, il n’y a plus d’éléments précédents !

109 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		22	22	92	32	10	94	21	70

			15
			⭡
			cle

On arrête donc les décalages à cette étape : on a trouvé la position d’insertion !

110 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		22	22	92	32	10	94	21	70

		15
		⭡
		cle

On peut maintenant insérer la clé dans la case libérée !

111 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		22	22	92	32	10	94	21	70
		⭡
		15
		⭡
		cle

On peut maintenant insérer la clé dans la case libérée !

112 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		15	22	92	32	10	94	21	70
		⭡
		15
		⭡
		cle

On peut maintenant insérer la clé dans la case libérée !

113 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		15	22	92	32	10	94	21	70

		15
		⭡
		cle

À la fin de l’étape, le tableau a retrouvé l’ensemble des éléments qu’il contenait au départ.

114 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		15	22	92	32	10	94	21	70

		15
		⭡
		cle

Noter que l’on voit grandir progressivement la zone triée du tableau.

115 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j			i
	⬇			⬇
	-1	0	1	2	3	4	5	6	7
tab		15	22	92	32	10	94	21	70

		15
		⭡
		cle

Passons à l’étape suivante !

116 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

				i
				⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

Passons à l’étape suivante !

117 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

				i
				⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

				32
				⭡
				cle

118 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

			j	i
			⬇	⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

				32
				⭡
				cle

92 est le 1er élément précédent à décaler.

119 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

			j	i
			⬇	⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	32	10	94	21	70

				32
				⭡
				cle

92 est plus grand que la clé donc on le décale en faisant une copie à droite.

120 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j		i
		⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	92	10	94	21	70

				32
				⭡
				cle

92 est plus grand que la clé donc on le décale en faisant une copie à droite.

121 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j		i
		⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	92	10	94	21	70

			32
			⭡
			cle

Faut-il insérer la clé ici ?

122 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j		i
		⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	92	10	94	21	70

			32
			⭡
			cle

Oui car l’élément précédent est cette fois plus petit que la clé : 22 <= 32.

123 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j		i
		⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	92	10	94	21	70

			32
			⭡
			cle

On arrête donc les décalages à cette étape : on a trouvé la position d’insertion !

124 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j		i
		⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	92	92	10	94	21	70
			⭡
			32
			⭡
			cle

On peut maintenant insérer la clé dans la case libérée !

125 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j		i
		⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70
			⭡
			32
			⭡
			cle

On peut maintenant insérer la clé dans la case libérée !

126 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j		i
		⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

			32
			⭡
			cle

Passons à l’étape suivante !

127 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

					i
					⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

Passons à l’étape suivante !

128 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

					i
					⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

On suit les mêmes étapes.

129 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

					i
					⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

					10
					⭡
					cle

130 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

				j	i
				⬇	⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

					10
					⭡
					cle

92 > 10

On décale !

131 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

			j		i
			⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	92	94	21	70

				10
				⭡
				cle

92 > 10

On décale !

132 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

			j		i
			⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	92	94	21	70

				10
				⭡
				cle

32 > 10

On décale !

133 of 247

		j			i
		⬇			⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	32	92	94	21	70

			10
			⭡
			cle

32 > 10

On décale !

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

134 of 247

		j			i
		⬇			⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	32	92	94	21	70

			10
			⭡
			cle

22 > 10

On décale !

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

135 of 247

	j				i
	⬇				⬇
	0	1	2	3	4	5	6	7
tab	15	22	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

22 > 10

On décale !

136 of 247

	j				i
	⬇				⬇
	0	1	2	3	4	5	6	7
tab	15	22	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

15 > 10

On décale !

137 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

15 > 10

On décale !

138 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comme on est au début du tableau, il n’y a plus d’éléments précédents !

139 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

On arrête donc les décalages à cette étape : on a trouvé la position d’insertion !

140 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Dans ce cas, quel critère met fin à la recherche de la position d’insertion ?

141 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Dans ce cas, quel critère met fin à la recherche de la position d’insertion ?

j devient strictement négatif.

142 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Dans ce cas, quel critère met fin à la recherche de la position d’insertion ?

Donc la recherche doit continuer tant que …

j devient strictement négatif.

143 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Dans ce cas, quel critère met fin de la recherche de la position d’insertion ?

Donc la recherche doit continuer tant que :

j >= 0

j devient strictement négatif.

144 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70
		⭡
		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

145 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		10	15	22	32	92	94	21	70
		⭡
		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

146 of 247

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		10	15	22	32	92	94	21	70
		⭡
		10
		⭡
		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Passons à l’étape suivante !

147 of 247

						i
						⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10
	⭡
	cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Passons à l’étape suivante !

148 of 247

						i
						⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10					94
	⭡					⭡
	cle					cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

149 of 247

					j	i
					⬇	⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10					94
	⭡					⭡
	cle					cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

92 <= 94

Pas de décalage à cette étape !

150 of 247

							i
							⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10
	⭡
	cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Passons à l’étape suivante !

151 of 247

							i
							⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10						21
	⭡						⭡
	cle						cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

152 of 247

						j	i
						⬇	⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10						21
	⭡						⭡
	cle						cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

94 > 21

On décale !

153 of 247

					j		i
					⬇		⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	94	70
	⭡
	10					21
	⭡					⭡
	cle					cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

94 > 21

On décale !

154 of 247

					j		i
					⬇		⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	94	70
	⭡
	10					21
	⭡					⭡
	cle					cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

92 > 21

On décale !

155 of 247

				j			i
				⬇			⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	92	94	70
	⭡
	10				21
	⭡				⭡
	cle				cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

92 > 21

On décale !

156 of 247

				j			i
				⬇			⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	92	94	70
	⭡
	10				21
	⭡				⭡
	cle				cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

32 > 21

On décale !

157 of 247

			j				i
			⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	32	92	94	70
	⭡
	10			21
	⭡			⭡
	cle			cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

32 > 21

On décale !

158 of 247

			j				i
			⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	32	92	94	70
	⭡
	10			21
	⭡			⭡
	cle			cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

22 > 21

On décale !

159 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

160 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

15 <= 21

Donc on arrête les décalages !

161 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Dans ce cas, quel critère met fin à la recherche de la position d’insertion ?

15 <= 21

Donc on arrête les décalages !

162 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

tab[...] <= ...

Dans ce cas, quel critère met fin à la recherche de la position d’insertion ?

163 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

tab[j] <= cle

Dans ce cas, quel critère met fin à la recherche de la position d’insertion ?

164 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

tab[j] <= cle

Dans ce cas, quel critère met fin à la recherche de la position d’insertion ?

Donc la recherche doit continuer tant que :

...

165 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

tab[j] <= cle

Dans ce cas, quel critère met fin à la recherche de la position d’insertion ?

Donc la recherche doit continuer tant que :

tab[j] > cle

166 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡		⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Terminons l’étape !

167 of 247

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	70
	⭡		⭡
	10		21
	⭡		⭡
	cle		cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Terminons l’étape !

168 of 247

								i
								⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	70
	⭡
	10
	⭡
	cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Passons à la dernière étape!

169 of 247

								i
								⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	70
	⭡
	10							70
	⭡							⭡
	cle							cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

170 of 247

							j	i
							⬇	⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	70
	⭡
	10							70
	⭡							⭡
	cle							cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

94 > 70

On décale !

171 of 247

						j		i
						⬇		⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	94
	⭡
	10						70
	⭡						⭡
	cle						cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

94 > 70

On décale !

172 of 247

						j		i
						⬇		⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	94	94
	⭡
	10						70
	⭡						⭡
	cle						cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

92 > 70

On décale !

173 of 247

					j			i
					⬇			⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	92	94
	⭡
	10					70
	⭡					⭡
	cle					cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

92 > 70

On décale !

174 of 247

					j			i
					⬇			⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	92	94
	⭡
	10					70
	⭡					⭡
	cle					cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

32 <= 70

On arrête les décalages !

175 of 247

					j			i
					⬇			⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	92	92	94
	⭡					⭡
	10					70
	⭡					⭡
	cle					cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

176 of 247

					j			i
					⬇			⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡					⭡
	10					70
	⭡					⭡
	cle					cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

177 of 247

								i
								⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡
	10
	⭡
	cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Algorithme terminé : tableau trié !

178 of 247

Sommaire. Tri par insertion

Principe
Implémentation en Python
Complexité

179 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): ...

	i
	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

	92
	⭡
	cle

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

180 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): ...

	i
	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

Que faut-il écrire ici ?

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

181 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): ...

	i
	⬇
	0	1	2	3	4	5	6	7
tab	92	22	15	32	10	94	21	70

Que faut-il écrire ici ?

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

État initial

182 of 247

								i
								⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡
	10
	⭡
	cle


1 2 3 4 5 6 7 8	def tri_insertion(tab): ...

Que faut-il écrire ici ?

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

État final

183 of 247

								i
								⬇
	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡
	10
	⭡
	cle


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

État final

184 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Que faut-il écrire ici ?

					i
					⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

					10
					⭡
					cle

Exemple de début d’étape

185 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Que faut-il écrire ici ?

					i
					⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

					10
					⭡
					cle

Exemple de début d’étape

186 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i]

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Que faut-il écrire ici ?

					i
					⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

					10
					⭡
					cle

Exemple de début d’étape

187 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = ... while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Que faut-il écrire ici ?

188 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = ... while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Commençons par l’initialisation de j.

189 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = ... while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Commençons par l’initialisation de j.

				j	i
				⬇	⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	92	10	94	21	70

					10
					⭡
					cle

Début de boucle while (exemple 1)

190 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = ... while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Commençons par l’initialisation de j.

						j	i
						⬇	⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10						21
	⭡						⭡
	cle						cle

Début de boucle while (exemple 2)

191 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Commençons par l’initialisation de j.

						j	i
						⬇	⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10						21
	⭡						⭡
	cle						cle

Début de boucle while (exemple 2)

192 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comment varie j d’une itération à l’autre ?

Exemple.

						j	i
						⬇	⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	21	70
	⭡
	10						21
	⭡						⭡
	cle						cle

193 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comment varie j d’une itération à l’autre ?

Exemple.

					j		i
					⬇		⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	94	94	70
	⭡
	10					21
	⭡					⭡
	cle					cle

194 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comment varie j d’une itération à l’autre ?

Exemple.

				j			i
				⬇			⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	92	92	94	70
	⭡
	10				21
	⭡				⭡
	cle				cle

195 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... j = ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comment varie j d’une itération à l’autre ?

Exemple.

			j				i
			⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	32	92	94	70
	⭡
	10			21
	⭡			⭡
	cle			cle

196 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... j = j - 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comment varie j d’une itération à l’autre ?

Exemple.

			j				i
			⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	32	92	94	70
	⭡
	10			21
	⭡			⭡
	cle			cle

197 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comment varie j d’une itération à l’autre ?

Exemple.

			j				i
			⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	32	32	92	94	70
	⭡
	10			21
	⭡			⭡
	cle			cle

198 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... = ... j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Quelle affectation

permet de réaliser un décalage (copie vers la droite)

199 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... = ... j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Quelle affectation

permet de réaliser un décalage (copie vers la droite)

		j			i
		⬇			⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	32	92	94	21	70

Exemple.

200 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: ... = ... j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Quelle affectation

permet de réaliser un décalage (copie vers la droite)

		j	j+1		i
		⬇	⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	32	92	94	21	70

Exemple.

201 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: tab[...] = tab[...] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Quelle affectation

permet de réaliser un décalage (copie vers la droite)

		j	j+1		i
		⬇	⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	32	92	94	21	70

Exemple.

202 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Quelle affectation

permet de réaliser un décalage (copie vers la droite)

		j	j+1		i
		⬇	⬇		⬇
	0	1	2	3	4	5	6	7
tab	15	22	32	32	92	94	21	70

Exemple.

203 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Quel(s) critère(s) indiquent que la position d’insertion n’a pas encore été trouvée ?

204 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Exemple 1. Pourquoi la recherche a-t-elle pris fin à cette étape ?

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

205 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Exemple 1. Pourquoi la recherche a-t-elle pris fin à cette étape ?

car tab[...] <= ...

206 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Exemple 1. Pourquoi la recherche a-t-elle pris fin à cette étape ?

car tab[j] <= cle

207 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while ...: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Le critère de continuation est donc le contraire.

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Exemple 1. Pourquoi la recherche a-t-elle pris fin à cette étape ?

car tab[j] <= cle

208 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Le critère de continuation est donc le contraire.

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Exemple 1. Pourquoi la recherche a-t-elle pris fin à cette étape ?

car tab[j] <= cle

209 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j					i
		⬇					⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Exemple 1. Pourquoi la recherche a-t-elle pris fin à cette étape ?

car tab[j] <= cle

210 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

211 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Exemple 2. Pourquoi la recherche a-t-elle pris fin à cette étape ?

212 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Exemple 2. Pourquoi la recherche a-t-elle pris fin à cette étape ?

j < ...

213 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Exemple 2. Pourquoi la recherche a-t-elle pris fin à cette étape ?

j < 0

214 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle ... ...: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Le critère de continuation est donc le contraire.

Exemple 2. Pourquoi la recherche a-t-elle pris fin à cette étape ?

j < 0

215 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle ... j >= 0: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Le critère de continuation est donc le contraire.

Exemple 2. Pourquoi la recherche a-t-elle pris fin à cette étape ?

j < 0

216 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle ... j >= 0: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Quel opérateur logique doit-on utiliser ?

217 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle ... j >= 0: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Pour autoriser un décalage les deux conditions doivent être vraies.

218 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle and j >= 0: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Pour autoriser un décalage les deux conditions doivent être vraies.

219 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle and j >= 0: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

L’expression booléenne est-elle bien construite ?

220 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle and j >= 0: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

L’expression booléenne est-elle bien construite ?

Non, on risque une erreur d’accès au tableau. Le rang doit d’abord être validé !

221 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle and j >= 0: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

L’expression booléenne est-elle bien construite ?

Que faut-il faire ?

222 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while tab[j] > cle and j >= 0: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

L’expression booléenne est-elle bien construite ?

On change l’ordre des conditions !

223 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j					i
	⬇					⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

L’expression booléenne est-elle bien construite ?

On change l’ordre des conditions !

224 of 247


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 ...

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Il ne reste plus que la dernière étape

225 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j					i
		⬇	⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Exemple 1.

Comment obtient-on la position d’insertion ?


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 ...

226 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comment obtient-on la position d’insertion ?

	j					i
	⬇	⬇				⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Exemple 2.


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 ...

227 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

		j	j+1				i
		⬇	⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

Exemple 1.

Comment obtient-on la position d’insertion ?


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 ...

228 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

Comment obtient-on la position d’insertion ?

	j	j+1				i
	⬇	⬇				⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Exemple 2.


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 ...

229 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

	j	j+1				i
	⬇	⬇				⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Exemple 2.

En déduire la dernière ligne !


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 ...

230 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .

En déduire la dernière ligne !

	j	j+1				i
	⬇	⬇				⬇
	-1	0	1	2	3	4	5	6	7
tab		15	15	22	32	92	94	21	70

		10
		⭡
		cle

Exemple 2.


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 tab[j + 1] = cle

231 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 tab[j + 1] = cle

Noter les deux boucles imbriquées.

232 of 247

Algorithme du tri par insertion

On parcourt le tableau de gauche à droite.

Pour chaque étape :

On mémorise l’élément courant dans une variable clé.
Tant que l’on a pas trouvé la position d’insertion, on décale vers la droite les éléments précédents.
On place la clé dans la case “libérée” par les décalages .


1 2 3 4 5 6 7 8	def tri_insertion(tab): for i in range(len(tab)): cle = tab[i] j = i - 1 while j >= 0 and tab[j] > cle: tab[j + 1] = tab[j] j -= 1 tab[j + 1] = cle

Quelle complexité peut-on conjecturer ?

233 of 247

Sommaire. Tri par insertion

Principe
Implémentation en Python
Complexité

234 of 247

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

235 of 247

D’après-vous quel est le meilleur des cas ?

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

236 of 247

D’après-vous quel est le meilleur des cas ?

LE TABLEAU EST DÉJÀ TRIÉ !



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡
	10
	⭡
	cle

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

237 of 247

D’après-vous quel est le meilleur des cas ?

LE TABLEAU EST DÉJÀ TRIÉ !



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡
	10
	⭡
	cle

Combien d’étapes peut-on prévoir ?

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

238 of 247

D’après-vous quel est le meilleur des cas ?

LE TABLEAU EST DÉJÀ TRIÉ !



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡
	10
	⭡
	cle

Il n’y aura aucun décalage. Donc il y aura autant d’étapes que de cases dans le tableau

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

239 of 247

D’après-vous quel est le meilleur des cas ?

LE TABLEAU EST DÉJÀ TRIÉ !



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡
	10
	⭡
	cle

Quelle est donc la complexité dans ce cas ?

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

240 of 247

D’après-vous quel est le meilleur des cas ?

LE TABLEAU EST DÉJÀ TRIÉ !



	0	1	2	3	4	5	6	7
tab	10	15	21	22	32	70	92	94
	⭡
	10
	⭡
	cle

Quelle est donc la complexité dans ce cas ?

complexité LINÉAIRE

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

241 of 247

D’après-vous quel est le pire des cas ?

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

242 of 247

D’après-vous quel est le pire des cas ?

LE TABLEAUX EST TRIÉ DANS L’ORDRE DÉCROISSANT.



	0	1	2	3	4	5	6	7
tab	94	92	70	32	22	21	15	10
	⭡
	10
	⭡
	cle

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

243 of 247

D’après-vous quel est le pire des cas ?

LE TABLEAUX EST TRIÉ DANS L’ORDRE DÉCROISSANT.



	0	1	2	3	4	5	6	7
tab	94	92	70	32	22	21	15	10
	⭡
	10
	⭡
	cle

Quelle est donc la complexité dans ce cas ?

Contrairement au tri par sélection, le tri par insertion a un nombre d’étapes qui varie selon que le tableau est déjà trié en partie ou non.

244 of 247

Chaque case doit être décalée au début du tableau.

1 étape		94	92	70	32	22	21	15	10

2 étapes		92	94	70	32	22	21	15	10

3 étapes		70	92	94	32	22	21	15	10

4 étapes		32	70	92	94	22	21	15	10

5 étapes		22	32	70	92	94	21	15	10

6 étapes		21	22	32	70	92	94	15	10

7 étapes		15	21	22	32	70	92	94	10

8 étapes		10	15	21	22	32	70	92	94

245 of 247

1 étape		94	92	70	32	22	21	15	10

2 étapes		92	94	70	32	22	21	15	10

3 étapes		70	92	94	32	22	21	15	10

4 étapes		32	70	92	94	22	21	15	10

5 étapes		22	32	70	92	94	21	15	10

6 étapes		21	22	32	70	92	94	15	10

7 étapes		15	21	22	32	70	92	94	10

8 étapes		10	15	21	22	32	70	92	94

On retrouve le nombre d’étapes du tri par sélection.

Quelle est donc la complexité dans ce cas ?

246 of 247

1 étape		94	92	70	32	22	21	15	10

2 étapes		92	94	70	32	22	21	15	10

3 étapes		70	92	94	32	22	21	15	10

4 étapes		32	70	92	94	22	21	15	10

5 étapes		22	32	70	92	94	21	15	10

6 étapes		21	22	32	70	92	94	15	10

7 étapes		15	21	22	32	70	92	94	10

8 étapes		10	15	21	22	32	70	92	94

On retrouve le nombre d’étapes du tri par sélection.

Quelle est donc la complexité dans ce cas ?

complexité QUADRATIQUE

247 of 247

Comparaison des complexités (dans le pire des cas)

Algorithme	Recherche dichotomique	Recherche linéaire	Tri par sélection Tri par insertion
Complexité	Logarithmique	Linéaire	Quadratique
Notation	O(log(n))	O(n)	O(n²)
Nombre d’étapes	log₂(n)	n	0,5n² + 0,5n
10	4	10	55
100	7	100	5050
1000	10	1000	500500
Un million	20	10⁶	5 · 10¹¹
Un milliard	30	10⁹	5 · 10¹⁷

Taille n du tableau

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

								4

								5

								6

								7

10	11	15	17	18	19	23	25

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

15	17	19	23	11	25	18	10	4

11	15	17	19	23	25	18	10	5

11	15	17	19	23	25	18	10	6

								7

10	11	15	17	18	19	23	25

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

15	17	19	23	11	25	18	10	4

11	15	17	19	23	25	18	10	5

11	15	17	19	23	25	18	10	6

11	15	17	18	19	23	25	10	7

10	11	15	17	18	19	23	25

		j	j+1				i
		⬇	⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

								4

								5

								6

								7

10	11	15	17	18	19	23	25

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

15	17	19	23	11	25	18	10	4

11	15	17	19	23	25	18	10	5

11	15	17	19	23	25	18	10	6

								7

10	11	15	17	18	19	23	25

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

15	17	19	23	11	25	18	10	4

11	15	17	19	23	25	18	10	5

11	15	17	19	23	25	18	10	6

11	15	17	18	19	23	25	10	7

10	11	15	17	18	19	23	25

		j	j+1				i
		⬇	⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

								4

								5

								6

								7

10	11	15	17	18	19	23	25

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

15	17	19	23	11	25	18	10	4

11	15	17	19	23	25	18	10	5

11	15	17	19	23	25	18	10	6

								7

10	11	15	17	18	19	23	25

0	1	2	3	4	5	6	7	i

15	19	23	17	11	25	18	10	0

15	19	23	17	11	25	18	10	1

15	19	23	17	11	25	18	10	2

15	19	23	17	11	25	18	10	3

15	17	19	23	11	25	18	10	4

11	15	17	19	23	25	18	10	5

11	15	17	19	23	25	18	10	6

11	15	17	18	19	23	25	10	7

10	11	15	17	18	19	23	25

		j	j+1				i
		⬇	⬇				⬇
	0	1	2	3	4	5	6	7
tab	10	15	22	22	32	92	94	70
	⭡
	10		21
	⭡		⭡
	cle		cle