La question du tri est omniprésente en informatique (efficacité, coût...) mais dans d'autre domaines également, prenons comme exemple le jeu de carte. cliquez ici Triez le jeux de carte ci-dessous puis recommencez en vous questionnant sur la méthode choisie (nombre de manipulations ...)
Petite vidéo expliquant 3 sortes de tris
Tri par insertion
Un cas concret
Commençons par trier à la main un jeu de carte !
Cinq cartes vous ont été distribuées et vous les retournez une à une pour les ranger par ordre croissant dans votre main.
La première carte retournée est :
La deuxième carte retournée est :
Vous mettez cette carte à droite en tant que plus grosse ; votre main triée est alors :
La troisième carte retournée est :
Vous insérez cette carte entre le 5 et le 10 ; votre main triée est alors :
La quatrième carte retournée est :
Vous insérez cette carte entre le 8 et le 10 ; votre main triée est alors :
La dernière carte retournée est :
Vous insérez cette carte au debut ; votre main triée est alors :
Ainsi la liste des valeurs des cinq cartes obtenues [5, 10, 8, 9, 2] a été triée par des insertions successives en [2, 5, 8 , 9, 10]
Voici une visualisation de l'algorithme de tri par insertion avec une danse roumaine :
Le tri par insertion correspond au tri de cartes généralisé avec une liste de valeurs.
On considère les éléments de la liste un par un (comme pour les cartes) :
- le premier élément de la liste forme une liste triée à un seul élément,
- le deuxième élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais une liste triée à deux éléments,
- le troisième élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais une liste triée à trois éléments,
- ...
- le dernier élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais complètement trié la liste initiale.
Ecrire en pseudo code l'algorithme de tri par insertion
Voici donc le tri par insertion écrit en langage Python :
def tri_insertion(lst:list)->list:
for i in range(1,len(lst)):
elt=lst[i]
j=i
while elt < lst[j-1] and j > 0:
lst[j]=lst[j-1]
j-=1
lst[j]=elt
return lst
Tester temporairement votre code et analyser le script par étape, vous pouvez également vous rendre sur pythontutor.
Voici une liste de nombres à trier : [4,9,6,7,12,3].
Écrire la trace d'exécution (sous forme de tableau) de la fonction tri_insertion précédente en faisant apparaître les valeurs de i et de j considérées, l'élément à classer, la liste des éléments déjà triés et la liste complète (en partie) triée.
Tri par sélection
Un cas concret
Recommençons par trier un jeu de carte à la main !
Cinq cartes vous ont été distribuées et vous les avez toutes dans un ordre quelconque dans votre main.
Supposons que les cartes en main soient :
Pour trier les cartes, l'idée est de :
- balayer l'ensemble des cartes non encore triées afin d'y repérer la plus petite.
- cette plus petite carte restante est alors placée en première position des cartes pas encore triées.
Mise en œuvre de la démarche sur l'ensemble des cinq cartes :
Aucune carte n'a déjà été triée. Parmi les 5 de l'ensemble, la plus petite est le 2 (de carreau) :
Cette carte de valeur minimale est placée en première position par une permutation de deux cartes, d'où la nouvelle configuration :
Le 2 est déjà bien placé. Parmi les 4 cartes restantes, la plus petite est le 5 (de cœur) : par hasard, il est déjà bien placé :
Deux cartes sont déjà bien placées. Parmi les 3 cartes restantes, la plus petite est le 8 (de carreau) :
Cette carte restante de valeur minimale est placée en première position des cartes restantes par une permutation de deux cartes, d'où la nouvelle configuration :
Trois cartes sont déjà bien palcés. Parmi les 2 cartes restantes, la plus petite est le 9 (de pique) :
Cette carte restante de valeur minimale est placée en première position des cartes restantes par une permutation de deux cartes, d'où la nouvelle configuration :
La dernière carte restante non triée est forcément la plus grande de toutes : aucun nouveau changement n'est nécessaire pour obtenir finalement la liste entièrement triée :
Généralités
On considère les éléments de la liste un par un (comme pour les cartes) :
- le plus petit élément de la liste est mis en première position par permutation ; on a désormais un début de liste triée à un élément,
- le deuxième plus petit élément de la liste est rangé en seconde position par permutation ; on a désormais un début de liste triée à deux éléments,
- ...
- l'avant dernier plus petit élément de la liste est rangé en avant-dernière position par permutation : on a désormais complètement trié la liste initiale.
Ecrire en pseudo code l'algorithme de tri par sélection
Deux fonctions seront utiles pour écrire en python cet algorithme :
- la fonction
positionnerqui renvoie l'index du minimum d'une liste entre un index nommédepartet son dernier terme. Cette liste et l'indexdepartsont entrés comme paramètres. - la fonction
permuterqui permute deux éléments d'une liste extraite entrée comme paramètre, les deux index de ces éléments étant aussi entés comme paramètres.
positionner reçoit deux paramètres en entrée :
- lst qui est la liste étudiée,
- depart qui un nombre entier qui correspond à un index.
positionner renvoie l'index du minimum de la liste extraite entrée dont les termes sont compris entre l'index depart et le dernier.
Voici le code de la fonction positionner où deux lignes sont incomplètes :
def positionner(lst: list,depart :int) -> int:
pos = depart # pos stocke la position du minimum : lst[pos] sera donc le minimum trouvé
i= pos + 1
while i<len(lst):
.......................... # ligne 5
.......................... # ligne 6
i += 1
return pos Compléter le code des lignes 5 et 6 de la fonction positionner
Voici le code de la procédure permuter où les trois lignes permettant la permutation des valeurs sont incomplètes.
Cette procédure permuter reçoit en paramètres :
- une liste lst,
- deux entiers i1 et i2 représentants deux index de cases dans cette liste.
def permuter(lst: list, i1: int, i2: int) -> None:
a = ...................... # ligne 2
.......................... # ligne 3
.......................... # ligne 4
return None Proposer ci dessous un code pour les lignes 2 à 4 permettant de compléter la procédure permuter précédente :
En utilisant la fonction positionner et la procédure permuter, proposer une procédure tri_selection qui correspond à l'algorithme de tri par sélection, c'est à dire qui prend comme paramètre une liste et qui
trie cette liste triée par ordre croissante par la méthode de tri par sélection et qui ne renvoie rien.
Pensez à vérifier la procédure écrite, par exemple avec la liste suivante : [1,8,6,4,3,9,20,7].
Pour visualiser comment cet algorithme trie une liste quelconque, accéder à un site Web en cliquant sur l'image ci-dessous :
Un fois accédé.e à ce site, cliquer sur Trier pour lancer l'application.
Voici ci-contre une animation qui permet de visualiser le tri par sélection :
- les nombres sur fond jaune sont déjà triés,
- le nombre sur fond rouge est le minimum de ceux déjà étudiés parmi les nombres encore à trier,
- le nombre sur fond bleu est celui en cours d'étude (celui dont la valeur sera comparée au minimum actuel sur fond rouge),
- la double flèche noire signifie qu'il y a permutation des valeurs ciblées.
Essayons maintenant d'évaluer la complexité de nos tris par sélection et par insertion
Vous allez désormais calculer la complexité de l'algorithme de tri par insertion, rappelé ci-dessous, dans le pire des cas, c'est à dire dans le cas où toutes les valeurs sont triées dans l'ordre décroissant.
def tri_insertion(lst:list)->list:
for i in range(1,len(lst)): # le premier élément forme seul une liste classée
elt=lst[i] # élément à classer
j=i
while elt < lst[j-1] and j > 0: # permutation avec le précédent s'il est plus grand
lst[j]=lst[j-1]
j-=1
lst[j]=elt # placement au bon endroit
return lstVous allez désormais calculer la complexité de l'algorithme de tri par sélection, rappelé ci-dessous, dans le pire des cas, c'est à dire dans le cas où toutes les valeurs sont triées dans l'ordre décroissant.
# Les deux fonctions étudiées précédemment :
# la fonction de recherche de l'index du minimum :
def positionner(lst: list,depart :int) -> int:
pos = depart # pos stocke la position du minimum : lst[pos] sera donc le minimum trouvé
i= pos+1
while i<len(lst):
if lst[i] < lst[pos]: # cas où une valeur plus petite que le minimum est trouvée
pos = i
i += 1
return pos # index du minimum de la liste entre depart et dernière valeur
# la procédure d'échange de deux termes :
def permuter(lst: list, i1: int, i2: int) -> None:
a = lst[i1] # utilisation d'une variable temporaire pour stocker la valeur qui sera écrasée par remplacement par la seconde valeur
lst[i1] = lst[i2]
lst[i2] = a
return None # aucun retour : la permutation a eu lieu sur la liste lst qui est donc modifiée.
# Tri par sélection
def tri_selection(lst: list) -> None:
for i in range(len(lst)-1): # on balaie toute la liste
pos = positionner(lst, depart=i) # on cherche le minimum parmi les termes non encore triés
if pos != i: # cas où le minimum n'est pas placé juste après la partie déjà triée
permuter(lst, i1=i, i2=pos)
return None # aucun retour : la permutation a eu lieu sur la liste lst qui est donc modifiée.
On considère que :
- chaque affectation correspond à une opération,
- chaque comparaison correspond à une opération,
- chaque obtention du terme d'une liste à partir de son index correspond à une opération.
Il existe des tris plus rapides en temps que les deux tris vus dans ce cours, fusion, rapide... Nous en étudirons d'autres l'an prochain.
Savoir faire et Savoir
- Écrire un algorithme de tri par insertion.
- Écrire un algorithme de recherche d'un minimum dans une liste
- Écrire un algorithme de tri par sélection.
- Déterminer la complexité d'un algorithme de tri.
- permutation de deux termes d'une liste
- Complexité quadratique