from PIL import Image
from PIL.ImageDraw import Draw
from random import shuffle
def draw_cross(im, cross_color = (0, 0, 0)):
"""Dessine une croix de couleur cross_color (noire par défaut)
au milieu de l'image im"""
(w, h) = im.size
x_middle, y_middle = w//2, h//2
for x in range(w):
im.putpixel((x, y_middle), cross_color)
for y in range(h):
im.putpixel((x_middle, y), cross_color)
def draw_line(draw, l, row, palette, pix_size=4):
"""
Dessine la ligne de numéro row de l'image en associant à chaque élément x
de l un carré de taille pix_size et de couleur donnée dans palette.
"""
col = 0
for e in l:
pix = palette[e%len(palette)]
draw.rectangle(((col, row), (col+pix_size, row+pix_size)), pix)
col += pix_size
def draw_steps(steps, pix_size = 4):
"""
Le paramètre steps est une matrice (liste de listes de même taille)
d'entiers. Construit une image correspondant à cette matrice en associant
une couleur à chaque entier
"""
palette = [0] * 128
for i in range(32):
palette[i] = (255-8*i, 255, 255-8*i)
palette[32+i] = ( 8*i, 255-8*i, 0)
palette[64+i] = ( 255, 8*i, 0)
palette[96+i] = (255-8*i, 255-8*i, 0)
width = len(steps[0])*pix_size
height = len(steps)*pix_size
im = Image.new('RGB', (width, height), (255, 255, 255))
draw = Draw(im)
row = height-pix_size
for step in steps:
draw_line(draw, step, row, palette, pix_size)
row -= pix_size
return im
def bubble_sort_steps(l):
"""
Trie la liste l en utilisant bubble_sort ; retourne une liste des copies de
l à chaque étape de l'algo.
"""
last = len(l)
steps = []
while last > 0:
i_max = 0
for i in range(0, last-1):
steps.append(l.copy())
if l[i] > l[i+1]:
i_max = i+1
l[i], l[i+1] = l[i+1], l[i]
last = i_max
steps.append(l.copy())
return steps
def test_sort(n, sort_algo = bubble_sort_steps, filename="bubbles.png"):
"""
Le paramètre sort_algo doit être une fonction implémentant un algo de tri
et retournant une liste des différents états de la liste triées pendant
l'exécution de l'algo.
Construit une liste au hasard de taille n, la trie et dessine une image
correspondant à l'exécution du sort_algo sur cette liste
"""
l = list(range(n))
shuffle(l)
steps = sort_algo(l)
print("exécution en %d étapes de calcul" % len(steps))
im = draw_steps(steps)
im.save(filename)
print("%s sauvé" %filename)