Étiquette : Tri

Le tri rapide (QuickSort) choisir aléatoirement un élément (appelé pivot) et de le positionner à sa place définitive, en permutant tous les éléments pour que ceux qui sont inférieurs au pivot soient à sa gauche et que ceux qui sont supérieurs au pivot soient à sa droite.

L’opération est appelée le partitionnement. Pour chacune des sous-listes (ou sous-tableaux), on choisit aléatoirement un nouveau pivot et on répète l’opération de partitionnement. Ce processus est répété récursivement, jusqu’à ce que tous les éléments soit trié.

Le partitionnement consiste à :

• permuter le pivot avec le dernier élément du sous-tableau
• placer en début du sous-tableau les éléments inférieurs au pivot
• déplacer le pivot à droite du dernier élément déplacé en début de tableau (les autres éléments étant supérieur au pivot).

from random import randint 


#Choix d'un pivot aléatoirement
#128mots.com
def choix_pivot(tableau,premier: int,dernier: int):
	pivot = randint(premier,dernier) 
	print("La sous-liste non triée est : " + str(tableau[premier:dernier+1]))
	print("Le pivot choisi aleatoirement est l'indice " + str(pivot) + " de valeur =" + str(tableau[pivot]))
	return pivot

#Fonction pour effectuer le partitionnement du tableau
#Permutation de tous les éléments pour que ceux qui sont inférieurs au pivot
# soient à sa gauche et que tous ceux qui sont supérieurs au pivot 
#soient à sa droite. 
#128mots.com
def partitionner(tableau, debut: int, fin: int, pivot: int):
	#Etape 1 : on positionne le pivot à la fin de la sous-liste arbitrairement	
		#On permute le pivot et le dernier element
	print("Partitionnement de la sous-liste = " + str(tableau[debut:fin+1]))
	print("---Placement du pivot à la fin la sous-liste")
	permute(tableau, pivot, fin)
	print("---")

	j = debut #indice d'avancement dans le début de la sous-liste
	#Pour i du début de la sous-liste à la fin
	for i in range(debut,fin):	
	#Tous les élément inférieur au pivot sont placés au début de la sous-liste
		if(tab[i] <= tab[fin]):
		#Si la valeur est inférieure on déplace au début du tableau
		#Et que la valeur n'est pas déjà bien placée alors on déplace au début du tableau
			permute(tableau,i,j)
			j+=1	
	#On place le pivot à la bonne place en permuttant l'élément après le dernier trouvé comme inférieur au pivot
	print("**permutation du pivot")
	permute(tableau,fin,j)
	#on retourne la position de j qui est alors la nouvelle position du pivot dans le tableau
	return j	


#Fonction de permutation de deux élément d'un tableau
#128mots.com
def permute(tableau, indice1: int, indice2:int):
	print("Permutation de l'élément " + str(indice1) + " avec l'element " + str(indice2))
	print("**Avant permutation : " + str(tab))
	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(tab))

#Fonction de tri rapide d'une sous-liste d'un tableau
#128mots.com
def  tri_rapide(tableau,debut: int,fin: int):
	# Si on a une sous-liste qui contient au moins 2 éléments
	if debut < fin :
		#on choisit un pivot dans la sous-liste
		pivot = choix_pivot(tableau,debut,fin)
		#on déplace tout les élément inférieur au pivot à gauche du pivot
		pivot = partitionner(tableau,debut,fin,pivot)
		#recursion pour refaire l'algorithme sur la sous-liste à gauche du pivot trouvé
		tri_rapide(tableau,debut,pivot - 1)
		#recursion pour refaire l'algorithme sur la sous-liste à droite du pivot trouvé
		tri_rapide(tableau,pivot + 1,fin)


compteur_permutation = 0
tab = [111, 34, 22, 55, 4, 2, 1, 77]
tri_rapide(tab,0,len(tab)-1)
print("resultat final du tri : " + str(tab))
print("nombre de permutation : " + str(compteur_permutation))

La sortie du programme est la suivante :

La sous-liste non triée est : [111, 34, 22, 55, 4, 2, 1, 77]
Le pivot choisi aleatoirement est l'indice 6 de valeur =1
Partitionnement de la sous-liste = [111, 34, 22, 55, 4, 2, 1, 77]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 6 avec l'element 7
**Avant permutation : [111, 34, 22, 55, 4, 2, 1, 77]
**Apres permutation : [111, 34, 22, 55, 4, 2, 77, 1]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 0
**Avant permutation : [111, 34, 22, 55, 4, 2, 77, 1]
**Apres permutation : [1, 34, 22, 55, 4, 2, 77, 111]
La sous-liste non triée est : [34, 22, 55, 4, 2, 77, 111]
Le pivot choisi aleatoirement est l'indice 5 de valeur =2
Partitionnement de la sous-liste = [34, 22, 55, 4, 2, 77, 111]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 5 avec l'element 7
**Avant permutation : [1, 34, 22, 55, 4, 2, 77, 111]
**Apres permutation : [1, 34, 22, 55, 4, 111, 77, 2]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 1
**Avant permutation : [1, 34, 22, 55, 4, 111, 77, 2]
**Apres permutation : [1, 2, 22, 55, 4, 111, 77, 34]
La sous-liste non triée est : [22, 55, 4, 111, 77, 34]
Le pivot choisi aleatoirement est l'indice 4 de valeur =4
Partitionnement de la sous-liste = [22, 55, 4, 111, 77, 34]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 4 avec l'element 7
**Avant permutation : [1, 2, 22, 55, 4, 111, 77, 34]
**Apres permutation : [1, 2, 22, 55, 34, 111, 77, 4]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 2
**Avant permutation : [1, 2, 22, 55, 34, 111, 77, 4]
**Apres permutation : [1, 2, 4, 55, 34, 111, 77, 22]
La sous-liste non triée est : [55, 34, 111, 77, 22]
Le pivot choisi aleatoirement est l'indice 4 de valeur =34
Partitionnement de la sous-liste = [55, 34, 111, 77, 22]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 4 avec l'element 7
**Avant permutation : [1, 2, 4, 55, 34, 111, 77, 22]
**Apres permutation : [1, 2, 4, 55, 22, 111, 77, 34]
---
Permutation de l'élément 4 avec l'element 3
**Avant permutation : [1, 2, 4, 55, 22, 111, 77, 34]
**Apres permutation : [1, 2, 4, 22, 55, 111, 77, 34]
**permutation du pivot
Permutation de l'élément 7 avec l'element 4
**Avant permutation : [1, 2, 4, 22, 55, 111, 77, 34]
**Apres permutation : [1, 2, 4, 22, 34, 111, 77, 55]
La sous-liste non triée est : [111, 77, 55]
Le pivot choisi aleatoirement est l'indice 5 de valeur =111
Partitionnement de la sous-liste = [111, 77, 55]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 5 avec l'element 7
**Avant permutation : [1, 2, 4, 22, 34, 111, 77, 55]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
---
Permutation de l'élément 5 avec l'element 5
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**permutation du pivot
Permutation de l'élément 7 avec l'element 7
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
La sous-liste non triée est : [55, 77]
Le pivot choisi aleatoirement est l'indice 6 de valeur =77
Partitionnement de la sous-liste = [55, 77]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
---
Permutation de l'élément 5 avec l'element 5
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**permutation du pivot
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
resultat final du tri : [1, 2, 4, 22, 34, 55, 77, 111]
nombre de permutation : 10

Le nombre de permutation est 10 pour un tableau de 8 éléments.

La complexité moyenne du tri rapide est Θ(n log n) soit 7.22 pour un tableau de 8 éléments.