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.
