3 2 1 5 6 4 Tableau à trier

3 2 1 5 6 4 Maximum sélectionné
3 2 1 5 4 6 Déplacé en fin de liste
3 2 1 5 4 6 Maximum sélectionné
3 2 1 4 5 6 Déplacé en fin de sous-liste
3 2 1 4 5 6 Maximum sélectionné
3 2 1 4 5 6 Déplacé en fin de sous-liste
Chapitre 10 3 2 1 4 5 6 Maximum sélectionné
Déplacé en fin de sous-liste
2 1 3 4 5 6
2 1 3 4 5 6 Maximum sélectionné
1 2 3 4 5 6 Déplacé en fin de sous-liste

Algorithme de Tri par 1 2 3 4 5 6 Tableau trié.

10.1.3 Tri par sélection - Algorithme

insertion ● L’algorithme du tri par sélection, s’écrit :
TRI PAR SELECTION(T) :
N = longueur(T)
POUR i variant de N-1 à 1 par pas de -1:
k = indice du Maximum dans le sous-tableau de T allant jusqu’à
10.1 Rappel : Tri par sélection l’indice i
Echanger T[i] et T[k]
10.1.1 Tri par sélection - principe FIN POUR

● Vous avez probablement déjà programmé l’algorithme de tri par sélection. ● Correction du programme : Utiliser pour invariant de boucle la proposition :
”Après le p-ième passage dans la boucle les p derniers éléments du tableau sont à
● Son principe est très simple :
leur place définitive.” Par récurrence sur p :
Initialisation. Au premier passage, lorsque i=N-1, le maximum est déplacé à l’indice
Donné un tableau composé de N éléments : N-1, c’est à dire en dernière position qui est bien sa position définitive.
– Chercher dans le tableau l’élément maximal. Hérédité. Supposons que les p − 1 derniers éléments sont à leur place définitive. En
particulier ce sont les p − 1 plus grands éléments du tableau. Au p-ème passage,
– Le déplacer en fin de tableau. lorsque i = N − p, k est l’indice du plus grand élément parmi les N − (p − 1) plus petit
éléments. On le déplace avant les (p − 1) derniers éléments ; les p derniers éléments
– Recommencer avec le sous-tableau constitué des N − 1 premiers éléments.
du tableau sont alors à leur place définitive. cqfd.
● Son nom provient du fait qu’à chaque étape on SELECTIONNE le plus grand
élément du sous-tableau, avant de le déplacer en fin de sous-tableau. 10.1.4 Tri par sélection - code
On utilise une fonction qui recherche dans un tableau et retourne, l’indice du
maximum dans le sous-tableau de T des premier éléments jusqu’à l’indice i.
10.1.2 Tri par sélection - exemple
def indiceMax(T,i):# Cherche l’indice du max parmi indices <= i
● Code de couleurs : iMax = i
– En noir : Partie du tableau, non triée,
for k in range(i):
if T[iMax] < T[k]:
– En bleu : Partie du tableau triée,
iMax = k
– En rouge : Maximum sélectionné dans la partie non triée. return iMax

1
Chapitre 10: Tri par insertion Informatique - Lycée Thiers

10.2 Tri par insertion

def Tri Selection(T): 10.2.1 Tri par insertion - principe
N = len(T)
for i in range(N-1,0,-1): Etudions un autre algorithme de tri : le Tri par insertion. C’est celui que l’on
iMax = indiceMax(T,i) utilise habituellement dans la vie courante, par exemple, pour trier un paquet de
T[i], T[iMax] = T[iMax], T[i] carte :
On constitue (imaginairement) 2 tas :
1
N (N − 1)
Complexité : Dans tous les cas on effectue de l’ordre de : ∑ i = = – l’un dans la main droite, contenant toutes les cartes avant tri,
i=N −1 2
– l’autre dans la main gauche, contenant les cartes déjà triées,
Θ(N 2 ) opérations élémentaires : complexité quadratique dans le pire et le meilleur
des cas. (Ce n’est pas un algorithme efficace.) Initialement la main gauche est vide.
Chaque étape consiste à :
On modifie le code pour qu’il donne tous les états intermédiaires durant le tri :
– prendre la première carte du tas non trié
def Tri Selection(T):
N = len(T)
– L’insérer progressivement à sa bonne place dans le tas trié, en la faisant des-
for i in range(N-1,0,-1): cendre d’une position tant que sa valeur reste inférieure à celle de la carte
iMax = indiceMax(T,i) située en dessous-d’elle.
print(T, ” Selection dans [0,”, i,”]: indice”, iMax,”element:”,T[iMax])
T[i], T[iMax] = T[iMax], T[i] Après chaque étape le tas non trié contient une carte de moins, le tas trié une carte
de plus.
A la fin du tri la main droite est vide. La main gauche contient toutes les cartes,
In [1]: tri selection([3,2,5,1,6,4]) triées.
[3, 2, 5, 1, 6, 4] Selection dans [0, 5 ]: indice 4 element: 6
[3, 2, 5, 1, 4, 6] Selection dans [0, 4 ]: indice 2 element: 5
[3, 2, 4, 1, 5, 6] Selection dans [0, 3 ]: indice 2 element: 4 10.2.2 Tri par insertion - exemple
[3, 2, 1, 4, 5, 6] Selection dans [0, 2 ]: indice 0 element: 3
● Code de couleurs :
[1, 2, 3, 4, 5, 6] Selection dans [0, 1 ]: indice 1 element: 2
– En noir : Partie du tableau, non triée,
– En bleu : Partie du tableau triée,
Pour un tableau ordonné décroissant.
– En rouge : Elément à insérer dans la partie triée.
In [2]: tri selection([6,5,4,3,2,1]) 3 2 1 5 6 4 Tableau à trier
[6, 5, 4, 3, 2, 1] Selection dans [0, 5 ]: indice 0 element: 6 3 2 1 5 6 4 Premier élément
[1, 5, 4, 3, 2, 6] Selection dans [0, 4 ]: indice 1 element: 5 3 2 1 5 6 4 Deuxième élément
[1, 2, 4, 3, 5, 6] Selection dans [0, 3 ]: indice 2 element: 4 2 3 1 5 6 4 Inséré dans le tableau trié
[1, 2, 3, 4, 5, 6] Selection dans [0, 2 ]: indice 2 element: 3 2 3 1 5 6 4 Troisième élément
[1, 2, 3, 4, 5, 6] Selection dans [0, 1 ]: indice 1 element: 2 2 1 3 5 6 4 Inséré dans le tableau trié
1 2 3 5 6 4 ⋮
Pour un tableau déjà ordonné (croissant). Quatrième élément
1 2 3 5 6 4
1 2 3 5 6 4 Inséré dans le tableau trié
In [3]: tri selection([1,2,3,4,5,6])
1 2 3 5 6 4 Cinquième élément
[1, 2, 3, 4, 5, 6] Selection dans [0, 5 ]: indice 5 element: 6
1 2 3 5 6 4 Inséré dans le tableau trié
[1, 2, 3, 4, 5, 6] Selection dans [0, 4 ]: indice 4 element: 5
1 2 3 5 6 4 Dernier élément
[1, 2, 3, 4, 5, 6] Selection dans [0, 3 ]: indice 3 element: 4
1 2 3 5 4 6 Inséré dans le tableau trié
[1, 2, 3, 4, 5, 6] Selection dans [0, 2 ]: indice 2 element: 3
1 2 3 4 5 6 ⋮
[1, 2, 3, 4, 5, 6] Selection dans [0, 1 ]: indice 1 element: 2
1 2 3 4 5 6 Tableau trié.

page 2
Chapitre 10: Tri par insertion Informatique - Lycée Thiers

10.2.3 Tri par insertion - Algorithme 10.2.5 Tri par insertion : complexité
● Déterminons le nombre d’opérations élémentaires dans le pire et le meilleur
Le tri peut s’opérer directement sur le tableau passé en paramètre : on parle de
des cas en fonction de la taille N du tableau à trier.
Tri en place.
– 1 opération élémentaire pour retourner N = len(T)
En pseudo-code, l’algorithme de Tri par insertion s’écrit : – puis on répète N-1 fois ce qui est dans la boucle for :
(on prend pour convention que les éléments du tableau sont indicés à partir de 0, – 1 opération pour x = T[i] (lecture dans un tableau et affectation)
et donc jusqu’à longueur(tableau) - 1.) – 1 opération pour l’affectation k = i
Tri Par insertion(T) # T est le tableau à trier
– 1 à 2 opérations pour tester la condition du while
N = longueur(T) # N = longueur du tableau
# Balayage du tableau du 2ème jusqu’au dernier élément : – au plus N-1 décalages dans la boucle while :
Pour i variant de 1 à N-1: – 3 opérations (accès en lecture/écriture et décrémentation).
x = T[i] # C’est l’élément à insérer ● La complexité de l’algorithme est donc :
k = i # k est son indice – Dans le pire des cas majorée par l’ordre de :
# Insertion dans la partie triée :
Tant que k > 0 et T[k-1] > x: (N − 1) × (N − 1) = Θ(N 2 ) (quadratique)
´¹¹ ¹ ¹ ¹ ¹ ¸¹¹ ¹ ¹ ¹ ¹ ¶ ´¹¹ ¹ ¹ ¹ ¹ ¸¹¹ ¹ ¹ ¹ ¹ ¶
# Décalage d’un cran sur la gauche : for while
T[k] = T[k-1]
– Dans le meilleur des cas minorée par l’ordre de :
k = k-1
T[k] = x (N − 1) × 1 = Θ(N ) (linéaire)
®
´¹¹ ¹ ¹ ¹ ¹ ¸¹¹ ¹ ¹ ¹ ¹ ¶ while
for

● Montrons que ces bornes sont atteintes :

10.2.4 Tri par insertion - Code
– Dans le pire des cas : le cas d’un tableau ordonné dans le sens décroissant :
En python : Par exemple : N (N − 1) ⋯ 2 1
Lors de la i-ème insertion l’élément doit être inséré en tout début de tableau :
def tri insertion(T): # T est le tableau à trier
la boucle while s’exécute i − 1 fois ; de l’ordre exactement de i opérations
N = len(T) # N = longueur du tableau
pour l’insertion du i-ème élément. La complexité est exactement d’ordre :
# Balayage du tableau du 2eme jusqu’au dernier élément:
for i in range(1,N): N −1
∑ i = Θ(N )
2
x = T[i] # C’est l’élément à insérer (quadratique)
i=1
k = i # k est son indice
# Insertion dans la partie triée : – Dans le meilleur des cas : le cas d’un tableau ordonné dans le sens croissant :
while k > 0 and T[k-1] > x: Par exemple : 1 2 ⋯ (N − 1) N
# Décalage d’un cran sur la gauche : Lors de la i-ème insertion l’élément est déjà à la bonne place : la boucle
T[k] = T[k-1] while ne s’exécute pas ; de l’ordre d’1 opérations pour chaque insertion. La
k = k-1 complexité est exactement d’ordre :
T[k] = x
(N − 1) × 1 = Θ(N ) (linéaire)
return T # Si l’on souhaite retourner le résultat
Correction de l’algorithme. Considérer comme invariant de boucle : Ainsi :
1. Le tri par insertion est un tri en place : sa complexité en espace mémoire est
”Après le k-ième balayage les k premiers éléments du tableau sont ordonnés dans en O(1).
le sens croissant. ”
2. Le tri par insertion a une complexité (temporellle) :
(par récurrence sur k). (a) linéaire dans le meilleur des cas (i.e. le cas d’un tableau déjà trié).

page 3
Chapitre 10: Tri par insertion Informatique - Lycée Thiers

(b) quadratique dans le pires des cas (ce n’est pas un très bon algorithme de In [1]: tri insertion([3,2,5,1,6,4])
tri pour un grand nombre de données). [3, 2, 5, 1, 6, 4]
Insertion de 2 d’indice 1
[2, 3, 5, 1, 6, 4]
3. Cependant on démontre que dans le cas d’un petit nombre d’éléments à trier Insertion de 5 d’indice 2
(inférieur à ...) c’est le plus rapide en moyenne. Insertion de 1 d’indice 3
[2, 3, 1, 5, 6, 4]
4. Il est également très efficace lorsque le tableau est déjà presque trié. Par [2, 1, 3, 5, 6, 4]
exemple la complexité est linéaire si de plus tous les éléments sont à une [1, 2, 3, 5, 6, 4]
distance uniformément bornée (ne dépendant pas de N ) de leur position Insertion de 6 d’indice 4
finale. Ou lorsque le nombre d’éléments qui ne sont à la bonne place est Insertion de 4 d’indice 5
uniformément borné. [1, 2, 3, 5, 4, 6]
[1, 2, 3, 4, 5, 6]
Out[1]: [1, 2, 3, 4, 5, 6]
Conclusion : continuons à l’utiliser pour trier un paquet de carte (c’est le meilleur Cas d’une liste ordonnée dans le sens décroissant :
possible), mais nous allons voir que lorsque le nombre d’éléments à trier devient
In [2]: tri insertion([6,5,4,3,2,1])
grand, ce n’est plus celui à utiliser sur de grands tableaux très ”désordonnés”. [6, 5, 4, 3, 2, 1]
Insertion de 5 d’indice 1
[5, 6, 4, 3, 2, 1]
Insertion de 4 d’indice 2
[5, 4, 6, 3, 2, 1]
[4, 5, 6, 3, 2, 1]
Insertion de 3 d’indice 3
10.2.6 Tri par insertion - Exemples [4, 5, 3, 6, 2, 1]
[4, 3, 5, 6, 2, 1]
[3, 4, 5, 6, 2, 1]
Insertion de 2 d’indice 4
Modifions le code pour afficher les états intermédiaires et les insertions : [3, 4, 5, 2, 6, 1]
[3, 4, 2, 5, 6, 1]
def tri insertion(T): # T est le tableau à trier [3, 2, 4, 5, 6, 1]
[2, 3, 4, 5, 6, 1]
N = len(T) # N = longueur du tableau Insertion de 1 d’indice 5
print(T) # Affichage initial [2, 3, 4, 5, 1, 6]
[2, 3, 4, 1, 5, 6]
# Balayage du tableau du 2eme jusqu’au dernier élément: [2, 3, 1, 4, 5, 6]
for i in range(1,N): [2, 1, 3, 4, 5, 6]
x = T[i] # C’est l’élément à insérer [1, 2, 3, 4, 5, 6]
Out[2]: [1, 2, 3, 4, 5, 6]
k = i # k est son indice
print(”Insertion de”, T[i], ”d’indice”, i) # Annonce d’insertion ● Sur une liste déjà triée :
# Insertion dans la partie triée :
while k > 0 and T[k-1] > x: In[3]: tri insertion([1,2,3,4,5,6])
# Décalage d’un cran sur la gauche : [1, 2, 3, 4, 5, 6]
T[k] = T[k-1] Insertion de 2 d’indice 1
T[k-1] = x Insertion de 3 d’indice 2
k = k-1 Insertion de 4 d’indice 3
print(T) # Affichage insertion Insertion de 5 d’indice 4
return T # Si l’on souhaite retourner le résultat Insertion de 6 d’indice 5
Out[3]: [1, 2, 3, 4, 5, 6]

page 4