1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
| import time
import random
import matplotlib.pyplot as plt
def maxi(l,n):
indice=0
for i in range(n):
if l[i]>l[indice]:
indice=i
return [l[indice],indice]
def tri_selec(l):
tps = time.clock()
i = len(l) - 1
while i>0:
j = maxi(l, i+1)[1]
if j != i:
l[j], l[i] = l [i], l[j]
i -= 1
duree = time.clock() - tps
return l, duree
def insertion(l,n):
while n>0 and l[n]<l[n-1]:
l[n-1],l[n]=l[n],l[n-1]
n-=1
return l
def tri_inser(l):
tps = time.clock()
n = len(l)
for i in range(1, n):
l = insertion(l, i)
duree = time.clock() - tps
return l, duree
def tri_rapide(L):
tps = time.clock()
def tri_aux(l):
if l==[]:
return []
return tri_aux([x for x in l[1:] if x<l[0]]) + \
[l[0]] + \
tri_aux([x for x in l[1:] if x>=l[0]])
L = tri_aux(L)
duree = time.clock()-tps
return L, duree
def liste_alea(n):
return [random.randint(0, 1000) for _ in range(n)]
def courbes(m, n):
X = range(n)
Y = [(sum(tri_selec(liste_alea(x))[1] for _ in range(m)) / m) for x in X]
plt.plot(X, Y)
Y = [(sum(tri_inser(liste_alea(x))[1] for _ in range(m)) / m) for x in X]
plt.plot(X, Y)
Y = [(sum(tri_rapide(liste_alea(x))[1] for _ in range(m)) / m) for x in X]
plt.plot(X, Y)
plt.legend(['selec', 'inser', 'rapide'])
plt.show() |
Partager