Tri par sélection

 

Le tri par sélection consiste à sélectionner le plus petit élément d’une suite de nombre pour le placer en premier par permutation avec le premier existant s’il n’est pas déjà le plus petit de la liste. Il faut ensuite recommencer avec la suite de nombre restante.

Le raisonnement est identique en prenant le plus grand élément et en le plaçant en dernier.

 

 

Cela donne par exemple :

[ 6 4 2 9 7 ]

> [ 2 4 6 9 7 ]

> [ 2 4 6 9 7 ]

> [ 2 4 6 9 7 ]

> [ 2 4 6 7 9 ]

 

 

L’algorithme s’écrit donc pour une liste maListe:

 

Entrèe : maListe liste de nb nombres.

 

Traitement du tri_par_selection :

 

Pour i de 0 à nb−1

ind_min = i

Pour j de i+1 à nb

Si maListe[j]<maListe[i]

alors indiceMin = j

finSi

finPour

Si j différent de ind_min

Permutation de maListe[i] et maListe[ind_min]

finSi

finPour

 

Sortie: liste maListe triée

 

 

On peut alors écrire en Python :

 

	
	def tri_par_selection(maListe):
	nb=len(maListe) 
	# stocke le nombre d’éléments de la liste maListe dans nb
	for i in range(nb-1) :
	# on cherche l'indice de l'élément le plus petit de la liste maListe de l'indice i à nb-1, le premier indice étant 0
		ind_min = i 
		# on considère que l'élément le plus petit  entre tous les éléments de i à nb-1 est à l’indice i
		for j in range( i+1,nb) :
		# on teste tous les éléments d'indice j de i+1 à nb
			if maListe[j]<maListe[ind_min] : 
			# Si on trouve un élément tel que maListe[j]< maListeL[ind_min] on change l'indice ind_min
				ind_min = j
		if i!=ind_min : 
		# si i est différent de ind_min on permute maListe[i] avec maListe[ind_min]
			maListe[i],maListe[ind_min]= maListe[ind_min],maListe[i] 
	return maListe 
	# renvoie  maListe triée

 

 

Tri par fusion

 

Le tri par fusion consiste à :

- s’il y a une seule valeur la liste est forcément triée

- s’il y a au moins deux valeurs, couper la liste en deux (partie entière), trier récursivement (on appelle la fonction de tri par fusion dans la fonction elle-même) les deux sous-listes obtenues puis fusionner les résultats : la fusion consiste à rassembler dans une seule liste triée les valeurs contenues dans les deux sous-listes triées fournies en paramètre (en gardant les éventuelles valeurs identiques dans les 2 listes : la longueur du résultat de la fusion est donc la somme des longueurs des deux listes initiales).

 

 

Cela donne avec l’exemple :

[ 6 4 2 9 7 ]

> [ 6 4 ] [ 2 9 7 ]

> [ 6 ] [ 4 ] [ 2 9 ] [ 7 ]

> [ 6 ] [ 4 ] [ 2 ] [ 9] [ 7 ]

> [ 6 ] [ 4 ] [ 2 9 ] [ 7 ]

> [ 4 6 ] [ 2 7 9 ]

> [ 2 4 6 7 9 ]

 

 

L’algorithme de tri_fusion s’écrit donc pour une liste maListe:

 

Entrèe : maListe liste de nb nombres.

 

Traitement du tri_fusion :

 

si taille de maListe < 2

Sortie: liste maListe triée

finSi

 

Sinon

couper la liste en 2

Sortie: fusion du tri_fusion de la première sous-liste et du tri_fusion de la deuxième sous-liste

finSinon

 

 

 

 

 

 

Et l’algorithme de fusion :

 

Entrèe : listeTriee1 et listeTriee2

 

Traitement de la fusion :

initialiser i1 et i2 à 0, n1=taille de listeTriee1 , n2 = taille de listeTriee2

créer une liste vide listeFusionnee

Tant que i1<n1 et i2<n2

si listeTriee1[i1]<listeTriee2[i2]

ajouter l’élément listeTriee1[i1] à la liste listeFusionee

i1 prend la valeur i1+1

finSi

Sinon

ajouter l’élément listeTriee2[i2] à la liste listeFusionee

i2 prend la valeur i2+1

finSinon

si i1=n1

ajouter la fin de la listeTriee2 à la liste listeFusionnee

finSi

Sinon

ajouter la fin de la listeTriee1 à la liste listeFusionnee

finSinon

 

Sortie: listeFusionnee

 

 

On peut alors écrire les 2 fonctions en Python :

 


def fusion(listeTriee1,listeTriee2):

	i1,i2,n1,n2=0,0,len(listeTriee1),len(listeTriee2)
	# initiallise i1 et i2 à 0, stockent les tailles des 2 listes dans n1 et n2
	listeFusionee=[]
	# crée la liste listeFusionee vide
	while i1<n1 and i2<n2: 
	# tant que la fin d’une des listes n’est pas atteinte
		if listeTriee1[i1]<listeTriee2[i2]:  
			listeFusionee.append(listeTriee1[i1]) 
			# ajoute l’élément listeTriee1[i1] à listeFusionnee si Triee1[i1]<listeTriee2[i2]
			i1+=1 
		else:  
			listeFusionee.append(listeTriee2[i2])
			# ajoute l’élément listeTriee2[i2] à listeFusionnee sinon
			i2+=1 
	if i1==n1:
		listeFusionee.extend(listeTriee2[i2:]) 
		# ajoute la fin de la listeTriee2 à listeFusionnee si i1=n1
	else:
		listeFusionee.extend(listeTriee1[i1:])
		# ajoute la fin de la listeTriee1 à listeFusionnee  sinon
	return listeFusionee

def tri_fusion(maListe):
	if len(maListe) < 2:
		return maListe
	else:
		m=len(maListe)//2
		return fusion(tri_fusion(maListe[:m]),tri_fusion(maListe[m:]))	

Free Joomla! template by L.THEME