"'O
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
1O.7 • Méthodes de tri
def tri_rapide(L ) :
if len(L)<=l :
r et urn ( L)
pivot =L. pop()
p et it s =[]
g rand s =[]
f or x i n L:
if x<=pivot:
petits. append( x)
e 1 se:
g rand s. append(x)
return( t ri _ rapide (petits) +[ pivot]+tri _ rapide(grands))
#####################Part i e principale ##########################
i mp or t t i me
i mp o r t r a n d o m
Lh= [ ]
for k in ran ge( I OO) :
L h . a p p e n d ( r a n d o m. r a n d o m( ) )
d e b u t = t i me . t i me ( )
tri_ se lect(Lh )
f i n = t i me . t i me ( )
p r i n t ( " Te mp s d ' e x é c u t i o n e n s e c o n d e s a v e c 1 e t r i p a r
sé le c ti o n : ", fin-debut)
Lh=[]
for k in ra nge( 100 ) :
L h . a p p e n d ( r a n d o m. r a n d o m( ) )
d e b u t = t i me . t i me ( )
tri_bulle s (Lh )
f i n = t i me . t i me ( )
p r i n t ( " Te mp s d ' e x é c u t i o n e n s e c o n d e s a v e c 1 e t r i à b u 1 1 e s
" , f in-d e but )
Lh = [ ]
for k in r ange( I OO):
L h . a p p e n d ( r a n d o m. r a n d o m( ) )
d e b u t = t i me . t i me ( )
tri _ rapide(Lh )
f i n = t i me . t i me ( )
p r i n t ( " Te mp s d ' e x é c u t i o n e n s e c o n d e s a v e c 1 e t r i r a p i d e
" , fi n - debu t)
c) Résultats obtenus après exécution
Exemple d'exécution :
• Temps d'exécution en seconde avec le tri par sélection: 0.006999969482421875 .
• Temps d'exécution en seconde avec le tri à bulles: 0.006000041961669922.
• Temps d'exécution en seconde avec le tri rapide: 0.0009999275207519531.
Une répétition de plusieurs exécutions du programme montre que le classement
de ces méthodes de tri, de la plus rapide à la moins rapide, est : tri rapide, tri à bulles
et tri par sélection.
245