Les tris

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 :

5 coeur

La deuxième carte retournée est :

10 trèfle

Vous mettez cette carte à droite en tant que plus grosse ; votre main triée est alors :

5 coeur 10 trèfle

La troisième carte retournée est :

8 carreau

Vous insérez cette carte entre le 5 et le 10 ; votre main triée est alors :

5 coeur 8 carreau 10 trèfle

La quatrième carte retournée est :

9 pique

Vous insérez cette carte entre le 8 et le 10 ; votre main triée est alors :

5 coeur 8 carreau 9 pique 10 trèfle

La dernière carte retournée est :

2 carreau

Vous insérez cette carte au debut ; votre main triée est alors :

2 carreau 5 coeur 8 carreau 9 pique 10 trèfle

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 :

8 carreau 5 coeur 10 trèfle 2 carreau 9 pique

Pour trier les cartes, l'idée est de :

  1. balayer l'ensemble des cartes non encore triées afin d'y repérer la plus petite.
  2. 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) :

8 carreau 5 coeur 10 trèfle 2 carreau 9 pique

Cette carte de valeur minimale est placée en première position par une permutation de deux cartes, d'où la nouvelle configuration :

2 carreau 5 coeur 10 trèfle 8 carreau 9 pique

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é :

2 carreau 5 coeur 10 trèfle 8 carreau 9 pique

Deux cartes sont déjà bien placées. Parmi les 3 cartes restantes, la plus petite est le 8 (de carreau) :

2 carreau 5 coeur 10 trèfle 8 carreau 9 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 :

2 carreau 5 coeur 8 carreau 10 trèfle 9 pique

Trois cartes sont déjà bien palcés. Parmi les 2 cartes restantes, la plus petite est le 9 (de pique) :

2 carreau 5 coeur 8 carreau 10 trèfle 9 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 :

2 carreau 5 coeur 8 carreau 9 pique 10 trèfle

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 :

2 carreau 5 coeur 8 carreau 9 pique 10 trèfle

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 positionner qui renvoie l'index du minimum d'une liste entre un index nommé depart et son dernier terme. Cette liste et l'index depart sont entrés comme paramètres.
  • la fonction permuter qui 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.
Cette procédure ne retourne rien (comme toute procédure) mais échange le contenu des cases correspondant aux index i1 et i2.


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.

aller sur http://lwh.free.fr/pages/algo/tri/tri_selection.html
aller sur https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif

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 lst

Vous 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