# Juste pour l'affichage ; pas à connaître
from IPython.display import display, HTML
def table(t, vert=(), rouge=(), bleu=()):
# Couleurs : <https://clrs.cc/>
s = ["<table style='font-size:130%'>", "<tr>"]
for i, x in enumerate(t):
couleur = "#2ECC40" if i in vert else ""
if i in rouge: couleur = "#FF4136"
if i in bleu: couleur = "#0074D9"
s.extend(['<td bgcolor="{}">'.format(couleur), str(x), '</td>'])
s.extend(["</tr>", "</table>"])
return s
def affiche(*args, **kwargs):
display(HTML(''.join(table(*args, **kwargs))))
def tri_insertion(t):
for i in range(len(t)):
j = i
while j > 0 and t[j]<t[j-1]:
t[j], t[j-1] = t[j-1], t[j]
j = j-1
def tri_insertion_affiche(t):
"""
Vert/Bleu : zone déjà triée (invariant)
Bleu : éléments comparés/échangés
Rouge : prochain élément à insérer
"""
affiche(t, [], [0])
for i in range(len(t)):
j = i
while j > 0 and t[j]<t[j-1]:
t[j], t[j-1] = t[j-1], t[j]
j = j-1
affiche(t, range(i+1), [i+1], range(j, i+1))
u = [2, 7, 3, 1, 4, 6, 5]
tri_insertion_affiche(u)
import random
v = [random.randrange(0, 100) for i in range(10)]
tri_insertion_affiche(v)
def pos_maxi(t, n):
pos = 0
for i in range(n):
if t[i] > t[pos]:
pos = i
return pos
def tri_selection(t):
for j in range(len(t), 0, -1):
p = pos_maxi(t, j)
t[j-1], t[p] = t[p], t[j-1]
def tri_selection_affiche(t):
"""
Vert/Bleu : zone déjà triée (invariant)
Bleu : éléments comparés/échangés
Rouge : prochain élément à insérer
"""
affiche(t, rouge=[len(t)-1])
for j in range(len(t), 0, -1):
p = pos_maxi(t, j)
t[j-1], t[p] = t[p], t[j-1]
affiche(t, range(j, len(t)), [j-2], [j-1, p])
v = [random.randrange(0, 100) for i in range(10)]
tri_selection_affiche(v)
# Juste pour l'affichage ! Pas à connaître
def trace(f):
from IPython.display import display, SVG
import graphviz
def show_trace():
s = ['digraph Trace {', 'node [shape=rectangle]', 'None [style=invis]']
nodes = []
for caller, current, label in trace.graph:
s.append('{} [label="{}"]'.format(current, label))
s.append('{}->{}'.format(caller, current))
s.extend('}')
trace.graph[:]=[]
display(SVG(graphviz.Source('\n'.join(s), engine='dot')._repr_svg_()))
def g(*args):
caller = None if trace.stack==[] else trace.stack[-1]
trace.compteur += 1
callee = trace.compteur
trace.stack.append(callee)
res = f(*args)
trace.graph.append((caller, callee, "{}{} = {}".format(f.__name__, args, res)))
trace.stack.pop()
if trace.stack==[]:
show_trace()
return res
trace.stack = []
trace.graph = []
trace.compteur = 0
return g
#@trace
def fusion(u, v):
res, i, j = [], 0, 0
while i < len(u) and j < len(v):
if u[i] < v[j]:
res.append(u[i])
i += 1
else:
res.append(v[j])
j += 1
return res+u[i:]+v[j:]
@trace
def tri_fusion(t):
n = len(t)
if n < 2:
return t
return fusion(tri_fusion(t[:n//2]), tri_fusion(t[n//2:]))
import random
v = [random.randrange(0, 100) for _ in range(6)]
print(v)
tri_fusion(v)
import random
@trace
def tri_rapide(t):
if len(t) < 2:
return t
valeur_pivot = t[0] # au hasard : t[random.randrange(len(t))]
petits, egaux, grands = [], [], []
for x in t:
if x < valeur_pivot:
petits.append(x)
elif x == valeur_pivot:
egaux.append(x)
else:
grands.append(x)
return tri_rapide(petits)+egaux+tri_rapide(grands)
import random
v = [random.randrange(0, 100) for _ in range(6)]
print(v)
tri_rapide(v)