1
|
import matplotlib
|
2
|
import matplotlib.pyplot
|
3
|
|
4
|
import random
|
5
|
import time
|
6
|
|
7
|
def insertion(tableau):
|
8
|
for etape in range(len(tableau)):
|
9
|
valeur_a_placer = tableau[etape]
|
10
|
indice_insertion = cree_place_pour_inserer(valeur_a_placer, etape, tableau)
|
11
|
|
12
|
tableau[indice_insertion] = valeur_a_placer
|
13
|
|
14
|
def cree_place_pour_inserer(valeur_a_inserer, indice_max_tableau, tableau):
|
15
|
position = indice_max_tableau
|
16
|
while position > 0 and ordre_non_respecte(tableau[position - 1], valeur_a_inserer):
|
17
|
decale_a_droite(tableau, position)
|
18
|
position = position - 1
|
19
|
|
20
|
return position
|
21
|
|
22
|
def ordre_non_respecte(valeur_petite, valeur_grande):
|
23
|
return valeur_grande < valeur_petite
|
24
|
|
25
|
def decale_a_droite(tableau, indice):
|
26
|
tableau[indice] = tableau[indice - 1]
|
27
|
|
28
|
def liste_aleatoire(n):
|
29
|
liste = []
|
30
|
for etape in range(n):
|
31
|
liste.append(random.randint(0, n))
|
32
|
|
33
|
return liste
|
34
|
|
35
|
def temps_tri(taille):
|
36
|
liste_a_trier = list(range(taille))
|
37
|
random.shuffle(liste_a_trier)
|
38
|
|
39
|
temps_actuel = time.process_time()
|
40
|
insertion(liste_a_trier)
|
41
|
delta = time.process_time() - temps_actuel
|
42
|
|
43
|
return delta
|
44
|
|
45
|
def trace_temps(taille_min, taille_max):
|
46
|
|
47
|
matplotlib.pyplot.ylabel("temps")
|
48
|
matplotlib.pyplot.xlabel("taille du tableau")
|
49
|
|
50
|
coordonnees_abcisses = range(taille_min, taille_max + 1)
|
51
|
temps = []
|
52
|
for x in coordonnees_abcisses:
|
53
|
temps.append(temps_tri(x))
|
54
|
|
55
|
matplotlib.pyplot.plot(coordonnees_abcisses, temps)
|
56
|
matplotlib.pyplot.show()
|
57
|
|
58
|
|
59
|
trace_temps(0, 100)
|