Stabilité d'un tri¶
Nous utilisons le tri à bulles pour illustrer une propriété importante des tris: la stabilité.
Cette propriété s'intéresse à ce qu'il se passe lorsque l'algorithme de tri rencontre deux éléments qu'il considère comme de même valeur.
TAB = [ ("Aubert","Beatrice"),
("Caron","Alain"),
("Bonnet","Christine"),
("Bonnet","Anne"),
("Aubert","Alexandre"),
("Caron","Catherine"),
("Bonnet","Benoit"),
("Aubert","Denis"),
("Aubert","Carole"),
("Caron","Brigitte") ]
On peut envisager de trier cette liste par
- nom de famille
- prénom
- nom/prénom
- prénom/nom
- ...
Pour le rendre plus générique - capable de trier selon divers critères - réécrivons notre tri à bulles avec une fonction de comparaison plus_petit passée en paramètre
def tri_a_bulles(T,plus_petit):
N = len(T)
for k in range(N,1,-1):
for i in range(0,k-1):
if plus_petit( T[i+1], T[i] ):
T[i],T[i+1] = T[i+1],T[i]
Pour trier la liste par ordre alphabétique des prénoms, il suffit d'écrire une fonction de comparaison sur le deuxième élément du tuple
def compare_prenoms(a,b):
return a[1] < b[1]
T1 = TAB.copy()
tri_a_bulles(T1,compare_prenoms)
afficher(T1)
Pour trier selon l'ordre alphabétique des noms, il suffit d'utiliser la fonction de comparaison
def compare_noms(a,b):
return a[0] < b[0]
T2 = TAB.copy()
tri_a_bulles(T2,compare_noms)
afficher(T2)
Appliquons le tri par nom de famille à la liste T1, précédemment triée par prénom.
T3 = T1.copy()
tri_a_bulles(T3,compare_noms)
afficher(T3)
Pour chaque nom de famille, les personnes sont triées par ordre alphabétique des prénoms
Un algorithme de tri est stable s'il ne modifie pas l'ordre initial des clés identiques.
Déstabiliser un tri stable¶
Dans l'algoritme du tri à bulle, remplaçons if plus_petit( T[i+1], T[i] ) par if not plus_petit( T[i], T[i+1] ):
Cela revient à remplacer $T_{i+1} < T_i$ par $\neg( T_i < T_{i+1} )$, i.e. $T_{i+1} \leq T_{i}$.
def tri_instable(T,plus_petit):
N = len(T)
for k in range(N,1,-1):
for i in range(0,k-1):
if not plus_petit( T[i], T[i+1] ):
T[i],T[i+1] = T[i+1],T[i]
Ce changement modifie le traitement des éléments égaux.
Avec
T[i] > T[i+1], les éléments égaux restent en place.Avec
T[i] >= T[i+1], les éléments égaux sont échangés.
Cela rend le tri instable. Trions de nouveau par nom de famille la liste T1 triée par prénom.
T4 = T1.copy()
tri_instable(T4,compare_noms)
afficher(T4)
Il est également possible de déstabiliser la fonction tri_a_bulles sans la modifier mais en lui fournissant en paramètre une mauvaise fonction de comparaison.
def compare_noms_instable(a,b):
return a[0] <= b[0]
T5 = T1.copy()
tri_a_bulles(T5,compare_noms_instable)
afficher(T5)
Stabiliser un tri instable¶
De même, il est toujours possible de stabiliser un algorithme de tri instable en procédant en trois étapes.
- Ajouter un indice
def ajoute_indice(T):
return [ (nom, prenom, indice) for indice, ( nom, prenom ) in enumerate(T)]
T6 = ajoute_indice(T1)
print(T6)
- Trier en utilisant l'indice pour différencier les éléments égaux par ailleurs.
def compare_noms_indices(a,b):
(nom_a, prenom_a, indice_a) = a;
(nom_b, prenom_b, indice_b) = b;
if(nom_a < nom_b):
return True
elif nom_a == nom_b:
return indice_a < indice_b
else:
return False
tri_instable(T6,compare_noms_indices)
print(T6)
- Oter l'indice des éléments triés
def retire_indice(T):
return [ (nom, prenom) for (nom, prenom, indice) in T ]
T6 = retire_indice(T6)
afficher(T6)
Visualisation¶
Pour analyser la stabilité des tris suivants, nous utiliserons une technique plus visuelle. Elle consiste à trier une liste de 50 nombres réels aléatoires entre 0 et 7 avec trois critères de tris distincts qui comparent
- les nombres originaux
- leurs parties entières
- leurs parties fractionnaires
def comp(a,b):
return a<b
def comp_int(a,b):
return int(a) < int(b)
def comp_frac(a,b):
return (a-int(a)) < (b - int(b))
Visualisons le tri de 50 nombres aléatoires
import numpy as np
import matplotlib.pyplot as plt
def comp_frac(a,b):
return (a-int(a)) < (b - int(b))
T = np.random.uniform(0,7,50)
tri_a_bulles(T,comp_frac)
plt.stem(T,markerfmt=',',linefmt='black',basefmt='black')
plt.show()
def comp_int(a,b):
return int(a) < int(b)
T = np.random.uniform(0,7,50)
tri_a_bulles(T,comp_int)
plt.stem(T,markerfmt=',',linefmt='black',basefmt='black')
plt.show()
T = np.random.uniform(0,7,50)
tri_a_bulles(T,comp_frac)
tri_a_bulles(T,comp_int)
plt.stem(T,markerfmt=',',linefmt='black',basefmt='black')
plt.show()
T = np.random.uniform(0,7,50)
tri_instable(T,comp_frac)
tri_instable(T,comp_int)
plt.stem(T,markerfmt=',',linefmt='black',basefmt='black')
plt.show()
|
© Olivier Cuisenaire, 2018 |