|
import matplotlib
|
|
import matplotlib.pyplot
|
|
|
|
import random
|
|
import time
|
|
|
|
def insertion(tableau):
|
|
for etape in range(len(tableau)):
|
|
valeur_a_placer = tableau[etape]
|
|
indice_insertion = cree_place_pour_inserer(valeur_a_placer, etape, tableau)
|
|
|
|
tableau[indice_insertion] = valeur_a_placer
|
|
|
|
def cree_place_pour_inserer(valeur_a_inserer, indice_max_tableau, tableau):
|
|
position = indice_max_tableau
|
|
while position > 0 and ordre_non_respecte(tableau[position - 1], valeur_a_inserer):
|
|
decale_a_droite(tableau, position)
|
|
position = position - 1
|
|
|
|
return position
|
|
|
|
def ordre_non_respecte(valeur_petite, valeur_grande):
|
|
return valeur_grande < valeur_petite
|
|
|
|
def decale_a_droite(tableau, indice):
|
|
tableau[indice] = tableau[indice - 1]
|
|
|
|
def liste_aleatoire(n):
|
|
liste = []
|
|
for etape in range(n):
|
|
liste.append(random.randint(0, n))
|
|
|
|
return liste
|
|
|
|
def temps_tri(taille):
|
|
liste_a_trier = list(range(taille))
|
|
random.shuffle(liste_a_trier)
|
|
|
|
temps_actuel = time.process_time()
|
|
insertion(liste_a_trier)
|
|
delta = time.process_time() - temps_actuel
|
|
|
|
return delta
|
|
|
|
def trace_temps(taille_min, taille_max):
|
|
|
|
matplotlib.pyplot.ylabel("temps")
|
|
matplotlib.pyplot.xlabel("taille du tableau")
|
|
|
|
coordonnees_abcisses = range(taille_min, taille_max + 1)
|
|
temps = []
|
|
for x in coordonnees_abcisses:
|
|
temps.append(temps_tri(x))
|
|
|
|
matplotlib.pyplot.plot(coordonnees_abcisses, temps)
|
|
matplotlib.pyplot.show()
|
|
|
|
|
|
trace_temps(0, 100)
|