[16, 30, 14, 56, 5, 0, 31, 26, 36, 80, 95, 0, 27, 85, 78, 78, 77, 73, 22, 47]
tab = [16, 30, 14, 56, 5, 0, 31, 26, 36, 80, 95, 0, 27, 85, 78, 78, 77, 73, 22, 47]
tab.sort()
print(tab)
Quelques liens pour découvrir et comparer des algorithmes de tris :
Au fait ce texte saisi dans une cellule du notebook d'IPython utilise le langage de balises Markdown, surcouche d'HTML.
t1 = [72, 29, 39, 59, 17, 54, 77, 79, 21, 6]
t2 = [22, 62, 63, 70, 98, 97, 9, 53, 2, 0]
t3 = [74, 82, 51, 22, 89, 49, 20, 12, 93, 84]
for t in [t1,t2,t3]:
t.sort()
print(t)
tri_selection.from random import randint
import time
def timetest(fonction):
"""exécute la fonction et affiche son temps d'exécution """
def fonction_modifiee(*args,**kargs):
tps_avant = time.time()
fonction(*args,**kargs)
tps_apres = time.time()
print("Le temps d'exécution de la fonction est de {:10.3e} s"
.format(tps_apres-tps_avant))
return fonction_modifiee
@timetest
def tri_selection(liste):
"""applique l'algorithme de tri par sélection à liste"""
n = len(liste)
for i in range(n-1):
minimum = i
for j in range(i+1,n):
if liste[j]<liste[minimum]:
minimum = j
if minimum != i:
z = liste[i]
liste[i] = liste[minimum]
liste[minimum] = z
def test(f,n,liste1,liste2,liste3):
"""fonction de test de la fonction de tri f
sur trois type d'entrées de taille n :
- uneliste1 d'entiers aléaloires
- une liste2 d'entiers triés dans l'ordre croissant
- une liste3 d'entiers triés dans l'orddre décroissant
"""
l1 = liste1[:]
l2 = liste2[:]
l3 = liste3[:]
print("Test sur une liste de {} entiers aléatoires entre 0 et {}".format(n,5*n).center(100,'*'))
f(l1)
print("Test sur une liste de {} entiers déjà triés".format(n).center(100,'*'))
f(l2)
print("Test sur une liste de {} entiers triés dans l'ordre inverse".format(n).center(100,'*'))
f(l3)
#pour le test du tri fusion il faut choisir une puissance de 2
n = eval(input('Entrez la taille souhaitée pour les listes d\'entiers: \n'))
print()
#initialisation des listes de test
liste1 = [randint(0,5*n) for i in range(n)]
liste2 = [i for i in range(n)]
liste3 = [n-i for i in range(n)]
#test de la fonction tri_selection
test(tri_selection,n,liste1,liste2,liste3)
Complexité du tri par sélection pour une liste de \(n\) entiers : chaque boucle interne de recherche du maximum dans la partie de \(n-i\) valeurs non encore triées, effectue \(n-i\) comparaisons ; donc l'algorithme nécessite \((n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}\) comparaisons. Il s'agit donc d'une complexité quadratique que la liste initiale soit déjà triée ou non (comme on peut le constater sur l'exemple ci-dessus).
Descriptions du tri par insertion :
Implémentation du tri par insertion en Python (voir ci-dessous)
Contrairement au tri par sélection, si l'on interrompt l'exécution de l'algorithme du tri par sélection après \(k\) étapes après \(k\) étapes, la sous-liste des \(k\) premiers éléments déjà triés n'est pas celle des \(k\) plus petits élements de la liste triée finale.
Analyse de complexité du tri par insertion :
La complexité du tri par insertion est donc quadratique dans le cas moyen et le pire des cas et linéaire dans le meilleur des cas (liste déjà triée). Cette bonne propriété que ne possèdent pas les tris par sélection ou par bulles, font du tri par insertion un tri efficace lorsqu'il y a peu de comparaisons ou que la liste est presque déjà triée. Une amélioration du tri par insertion, appelée Tri de Shell (voir Exercice 8) tire profit de cette propriété.
@timetest
def tri_insertion(liste):
"""applique l'algorithme de tri par insertion à liste"""
n=len(liste)
for j in range(1,n):
cle=liste[j]
i=j-1
while i>-1 and liste[i]>cle:
liste[i+1]=liste[i]
i=i-1
liste[i+1]=cle
#test de la fonction tri_insertion
n=10000
test(tri_insertion,n,liste1,liste2,liste3)
L'algorithme du tri par bulles consiste à trier un tableau en ne s'autorisant qu'à échanger deux éléments consécutifs de ce tableau. On peut démontrer que l'algorithme suivant trie n'importe quel tableau :
Descriptions du tri par bulles :
Implémentation en Python du Tri par bulles, coir ci-dessous plusieurs versions.
Selon l'implémentation tri_bulle1 ou tri_bulle2 (voir ci-dessous) la complexité du tri par bulles est quadratique (comme pour le tri par sélection) ou linéaire (comme pour le tri par insertion) sur les listes déjà triées.
Si on applique le tri par bulles à une liste triée dans l'ordre décroissant comme \([n,n-1,n-2,..,1]\), quelle que soit l'implémentation, on a besoin de \(i-1\) permutations (comparaison + échange) pour \(i\) allant de \(n\) à \(1\) soit un total de \((n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}\) permutations. La complexité du tri par bulles est donc quadratique sur les listes triées dans l'ordre inverse.
@timetest
def tri_bulle1(liste):
"""applique l'algorithme de tri à bulles à liste
inspiré de Algorithmqie de Cormen page 35 mais
sur les listes déjà triées la complexité n'est
pas linéaire.
la boucle extérieure fait n-1 tours pour faire remonter les n-1 plus grosses bulles
au i ème tour de boucle on a déjà fait remonter les i-1 plus grosses bulles qui sont à la fin.
La boucle intérieure parcourt alors les n-1-i plus petites bulles qui sont au début
pour faire remonter la plus grosse bulle parmi elles"""
n = len(liste)
for i in range(n-1):
for j in range(n-1-i):
if liste[j+1]<liste[j]:
z = liste[j]
liste[j] = liste[j+1]
liste[j+1] = z
@timetest
def tri_bulle2(liste):
"""applique l'algorithme de tri à bulles à liste
inspiré de celui proposé par wikipedia avec une
petite amélioration : à chaque fois qu'on a fait remonter
une bulle on réduit la liste de recherche.
La complexité est bien linéaire pour les listes déjà triées"""
n = len(liste)
test = True
i = 0
while test:
test = False
for j in range(n-1-i):
if liste[j+1]<liste[j]:
z = liste[j]
liste[j] = liste[j+1]
liste[j+1]=z
test = True
i = i+1
#test de la fonction tri_bulle2
n=10000
test(tri_bulle2,n,liste1,liste2,liste3)
Le tri de Shell est une amélioration du tri par insertion qui procède ainsi sur une liste L d'entiers :
Etape 1 On choisit une suite \(\left(p_{n}\right)\) d'entiers positifs appelés pas. Nous choisirons classiquement, la suite définie par \(p_{0}=1\) et \(p_{n+1}=3p_{n}+1\).
Etape 2 On calcule le plus grand terme \(p_{n}\) qui est inférieur à la taille de notre liste.
Etape 3 On trie alors par insertion chaque sous-liste d'éléments de L séparés de \(p_{n}\) positions. On applique donc \(p_{n}\) fois (pour départ allant de \(0\) à \(p_{n}-1\)) une procédure tri_insertion_pas(liste,depart,pas) qui trie par insertion une sous-liste de L d'éléments choisis toutes les \(p_{n}\) positions à partir de la position départ.
Etape 4 On recommence ensuite avec \(p_{n-1}\) et ainsi de suite par une boucle descendante jusqu'à \(p_{0}=1\). A cette étape on applique 1 fois la procédure tri_insertion_pas(liste,0,1) qui trie par insertion la liste. Mais ce n'est pas la liste initiale, c'est une liste affinée et presque déjà triée par application successives des procédures tri_insertion_pas(liste,depart,pas).
A la dernière étape,on ne trie pas par insertion la liste initiale, mais une liste affinée et presque déjà triée par application successives des procédures tri_insertion_pas(liste,depart,pas). Or le tri par insertion est de complexité linéaire sur les listes presque triées ... Le tri de Shell remplace ainsi les nombreux petits bonds du tri par insertion classique (permutation entre deux éléments successifs qui ne sont pas triés) par de moins nombreux mais plus grands bonds (permutations entre deux éléments non triés séparés d'un pas).
Comme on peut le constater ci-dessous, le tri de Shell est réellement plsu performant que le tri par insertion classique.
Pour une description plus détaillée, voir :
@timetest
def tri_shell(liste):
"""algorithme de tri par insertion de shell"""
def tri_insertion_pas(liste,depart,pas):
"""tri par insertion avec pas"""
n=len(liste)
j = pas+depart
while j<n:
cle=liste[j]
i=j-pas
while i>-1 and liste[i]>cle:
liste[i+pas]=liste[i]
i=i-pas
liste[i+pas]=cle
j = j + pas
pas = 1
while pas<len(liste):
pas =3*pas+1
#print(pas)
while pas>1:
pas = pas//3
#print(pas)
for k in range(pas):
tri_insertion_pas(liste,k,pas)
#print(liste)
#test de la fonction tri_shell
n=10000
test(tri_shell,n,liste1,liste2,liste3)
Descriptions du tri par fusion :
def fusion(tab,p,q,r):
"""procédurefusion qui fusionne en un seul segment ordonné
deux segments ordonnés du tableau tab, le premier allant de la
position p à la position q, le second de q+1 à r"""
#tableau qui va recevoir la fusion des deux segments ordonnés
tabfusion = []
#index j de positionnement dans le premier segment
#p<=j<=q
j = p
#index k de positionnement dans le premier segment
#q+1<=k<=r
k = q+1
#boucle sur les r-p+1 éléments du tableau
for i in range(r-p+1):
#on insère l'élément tab[j] du premier segment
#dans le segment fusionné
#s'il reste des éléments dans les 2 segments
#et que tab[i]<=tab[k]
#ou s'il ne reste plus d'élément dans el second segment
if (j<=q and k<=r and tab[j]<=tab[k]) or k>r:
tabfusion.append(tab[j])
#on se déplace de 1 dans le premier segment
j += 1
else:
tabfusion.append(tab[k])
#on se déplace de 1 dans le second segment
k += 1
return tabfusion
def test_exo10(fonctionfusion):
from random import randint
tab1 = [randint(0,20) for i in range(10)]
tab1.sort()
tab2 = [randint(0,20) for i in range(10)]
tab2.sort()
tab = tab1+tab2
print('tableau : ',tab)
print('segment 1 : ',tab1)
print('segment 2 : ',tab2)
return fonctionfusion(tab,0,9,19)
test_exo10(fusion)
def estpuissance2(n):
"""Teste si un entier n est une puissance de 2
et retourne None ou son exposant p tel que n=2**p"""
#variable contenant la puissance de 2
puissance = 1
#exposant
expo = 0
while puissance<n:
expo += 1
puissance *= 2
if puissance==n:
return expo
return None
def test_exo11_puissance2():
"""test de la fonction estpuissance2"""
tab = [0,1,2,16,25,10,1024]
for e in tab:
print(e, ' ',estpuissance2(e))
@timetest
def tri_fusion(tab):
"""tri par fusion (version itérative)
d'un tableau tab de taille 2^n.
Retourne None si la taille n'est pas une puissance de 2"""
#longueur du tableau
n = len(tab)
expo = estpuissance2(n)
#expoest le log binaire de n
#si expo est None (evalué à False) on retourne None
if not expo:
return None
#sinon n est une puissance de 2
#on paut faire le tri fusion
#initialisation de la taille des segments
#on boucle sur la longueur des segments
#tant que taillesegment<n
#ce qui fera expo=log2(n) tours
taillesegment = 1
while taillesegment<n:
#boucle interne sur les segments de longueur taillesegment
#on fusionne 2 par 2 les segments
#de longueur taillesegment qui sont consecutifs
#initialisation des index p de debut du premier segment
#q de fin du premier segment
#et r de fin du second segment
p,q,r = 0,taillesegment-1,2*taillesegment-1
#tant que l'index de fin du second segment
#n'est pas au bout du tableau
while r<=n-1:
#la partie de tab comprise entre les indices
#p et r est fusionnée
tab[p:r+1] = fusion(tab,p,q,r)
#mise à jour des index des 2 segments consécutifs
#on fait un saut d'index de longueur 2*taillesegment
#car on passe aux 2 segments consécutifs suivants
p,q,r = p+2*taillesegment,q+2*taillesegment,r+2*taillesegment
#tous les segments de longueur taillesegment ont été fusionnés
#on incrémente (fois 2) taillesegment
taillesegment *= 2
#test de la fonction estpuissance2
test_exo11_puissance2()
#test de la fonction tri_fusion, vérifions qu'elle trie bien
n=2**4
tab = [randint(0,100) for i in range(n)]
print(tab,id(tab))
tri_fusion(tab)
print(tab,id(tab))
#retourne None si la taille n'est pas une puissance de 2
print(tri_fusion([7,2,1]))
#test de complexité de la fonction tri_fusion
#avec une entrée de taille 2**10 soit environ 1000
#comme pour les autres fonctions de Tris
test(tri_fusion,n,liste1,liste2,liste3)