Archives des Tri par tas

L’algorithme du tri par tas est un algorithme de tri par comparaison. Cet article vous done le code du tri par tas python.

L'algorithme du tri par tas python est un algorithme de tri par comparaison. Cet article vous done le code du tri par tas python.

Le principe de l’algorithme du tri par tas python est le suivant :

Alors on recherche le père du dernier nœud de l’arbre et on le tamise : le père d’un noeud dans un arbre binaire corresponds à l’arrondi inférieur de (i-1)/2 avec i la position du noeud dans le tableau qui stocke l’arbre.
Le tamisage d’un noeud consiste à visiter son fils droit et son fils gauche et permuter la racine avec le plus grand des deux.
Et il faut tamiser l’arbre jusqu’à arriver à la racine, le plus grand nombre de l’arbre se retrouve alors en position de racine au début du tableau.
On permute la racine qui est le plus grand nombre avec la dernière feuille (soit la position n du tableau qui stocke l’arbre de taille n). On considère alors que ce nombre est bien ordonné (càd il est en dernière position et c’est le plus grand)
Enfin, l’opération de tamisage et permutation est réitérée en considérant le sous arbre qui va de la racine à n-1 (pour ne pas déplacer le nombre qui a été correctement ordonné) jusqu’à ce qu’on arrive au fils gauche de la racine (l’indice 1)

Voir le lien wikipedia : https://fr.wikipedia.org/wiki/Tri_par_tas

from math import *
#128mots.com
def indice_fils_gauche(noeud_pere:int):
	return (noeud_pere * 2)+ 1

def indice_fils_droit(noeud_pere:int):
	return (noeud_pere * 2) + 2
#Retourne l'indice du noeud pere si il existe (noeud doit être > 0)
def indice_noeud_pere(noeud):
	#Si il existe il s'agit de l'arrondi inférieur de (noeud-1)/2
	return floor((noeud - 1)/2)

#permute 2 éléments d'un tableau et incrément la variable globale compteur_permutation à initialiser dans le main
def permute(tableau, indice1: int, indice2:int):
	print("Permutation de l'élément " + str(indice1) + " avec l'element " + str(indice2))
	print("**Avant permutation : " + str(tableau))
	global compteur_permutation
	if(indice1 != indice2):
	#on sauvegarde la valeur de l'indice 1 dans une variable temporaire
		tmp = tableau[indice1]
		tableau[indice1] = tableau[indice2]
		tableau[indice2] = tmp
		compteur_permutation += 1
	print("**Apres permutation : " + str(tableau))

#Tamise un arbre binaire à partir d'un noeud en parametre
#1. on compare le noeud avec le fils droit et le fils gauche (si ils existent)
#2. on permute avec la plus grande valeur
#128mots.com
def tamise(arbre,noeud,longueur):
	#On visite le fils droit et le fils gauche
	print("++Tamisage de " + str(noeud) + " arbre: " + str(arbre))	
	indiceFilsDroit   = indice_fils_droit(noeud)
	indiceFilsGauche  = indice_fils_gauche(noeud)
	print("indiceFilsDroit>>" + str(indiceFilsDroit))
	print("indiceFilsGauche>>" + str(indiceFilsGauche))


	if(indiceFilsDroit < longueur): # si le fils droit existe
		if(arbre[indiceFilsDroit] > arbre[indiceFilsGauche]): #Si le fils droit est plus grand que le fils gauche
			if(arbre[indiceFilsDroit] > arbre[noeud]): #Si le fils droit est plus grand que le noeud tamisé
				permute(arbre,indiceFilsDroit,noeud)
		elif(arbre[indiceFilsGauche] > arbre[noeud]): #Si le fils gauche est supérieur au noeud tamisé alors on permute
			permute(arbre,indiceFilsGauche,noeud)
	elif(indiceFilsGauche < longueur): #Si le fils gauche existe
		if(arbre[indiceFilsGauche] > arbre[noeud]): #Si le fils gauche est supérieur au noeud tamisé alors on permute
			permute(arbre,indiceFilsGauche,noeud)
	print("++Apres tamisage : " + str(arbre))			
#128mots.com

compteur_permutation = 0
arbre = [11, 222, 3, 24, 5, 46, 67, 899] #On écrit un arbre sous forme de tableau
print("démarrage arbre : " + str(arbre))

#128mots.com
#Tamisage initial
#on prend le dernier élément de l'arbe qui est une feuille et on recherche son père
indiceDuNoeudPere = indice_noeud_pere(len(arbre)-1) 
#on tamise càd on compare le noeud pere avec le fils droit et le fils gauche
#puis on permute avec la plus grande valeur
for i in range(indiceDuNoeudPere,-1,-1): #On tamise jusqu'à la racine
	tamise(arbre,i,len(arbre))

permute(arbre,len(arbre)-1,0) #on permute le premier element et le dernier 
#suite au tamisage c'est la plus grande valeur on la place donc à la fin du tableau

#on répete le tamisage
for i in range(len(arbre)-1,1,-1): 
	indiceDuNoeudPereDeI = indice_noeud_pere(i-1) #on prend l'élément i de l'arbe qui est une feuille et on recherche son père
	for j in range(indiceDuNoeudPereDeI,-1,-1): #On tamise jusqu'à la racine
		tamise(arbre,j,i)
	permute(arbre,i-1,0)

print("resultat final du tri : " + str(arbre))
print("nombre de permutation : " + str(compteur_permutation))