Dans ce notebook, nous présentons interractivement différent algorithmes de tris et de partitionement:
Nous n'avons pas pu faire de la même manière le tri par fusion car celui-ci n'est pas "en place.
Vous pouvez, sans aucuns problèmes, ignorer ces fonctions
def trace_algo(cmd):
sort_gen = iter(cmd)
def bla(cmd=selector(["Step"],
buttons=True)):
global dessin
try:
mess, dessin = next(sort_gen)
except StopIteration:
mess = "======== Finished ======="
print(mess)
dessin.show(figsize=(7,4))
interact(bla)
SIZE_POINT=100
def plot_tab(tab):
return sum(point(v, size=SIZE_POINT) for v in
enumerate(tab))
def vert(i, tab, **opts):
return line([(i, 0),(i, max(tab)+1)], **opts)
def horiz(i, tab, **opts):
return line([(0,i),(len(tab)+1,i)], **opts)
L'instruction yield en python est une sorte de "return" qui quitte temporairement la fonction. On peut ensuite reprendre l'exécution. Voici un exemple:
def carres(n):
r"""
Génère la suite des carrées des nombres de 0 à n-1
"""
for i in range(n):
yield i*i
On peut, par exemple, parcourir les différents résultats avec une boucle for:
for c in carres(5):
print(c)
0 1 4 9 16
Ou les ranger dans une liste:
list(carres(9))
[0, 1, 4, 9, 16, 25, 36, 49, 64]
Le fonctionnement repose sur le protocol suivant:
it = carres(4); it
<generator object carres at 0x7f9bbceae500>
next(it)
0
next(it)
1
next(it)
4
next(it)
9
next(it)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) /tmp/ipykernel_8746/600241529.py in <module> ----> 1 next(it) StopIteration:
Il n'est pas important pour la suite de retenir ceci. On a juste besoin de savoir que yield nous permet d'introduire des points d'arrêt dans les fonctions.
def bubble_sort(T):
#########################################################
## dessin qui va être affiché lors des points d'arrêt ###
## vous pouvez complètement ingorer ce code.
def dessin():
return ("i=%i, j=%i"%(i,j),
sum(point((pos,v), size=SIZE_POINT,
color="blue" if pos <= i else "green")
for pos, v in enumerate(tab))
+vert(i+1/2,tab,color="green")
+vert(j+1/2,tab))
#########################################################
yield "Start", plot_tab(T) ## Point d'arret en début de boucle
for i in range(len(T)-1, 0, -1):
for j in range(i):
yield dessin() ## Point d'arret avant l'échange
if T[j] > T[j+1]:
T[j], T[j+1] = T[j+1], T[j]
yield dessin() ## Point d'arret après l'échange
tab = [randint(0, 20) for i in range(10)]
tab
[1, 0, 11, 8, 4, 20, 14, 11, 19, 10]
for _ in bubble_sort(tab): pass # On ignore les points d'arrêt.
tab
[0, 1, 4, 8, 10, 11, 11, 14, 19, 20]
tab = [randint(0, 20) for i in range(10)]
trace_algo(bubble_sort(tab))
Interactive function <function trace_algo.<locals>.bla at 0x7fe323492ae8> with 1 widget cmd: ToggleButtons(d…
def bubble_sort_2d(T):
#########################################################
## dessin qui va être affiché lors des points d'arrêt ###
## vous pouvez complètement ingorer ce code.
def dessin():
return ("i=%i, min=%i, max=%i"%(i,min,max),
sum(point((pos,v), size=SIZE_POINT,
color="blue" if min <= pos <= max else "green")
for pos, v in enumerate(tab))
+ vert(min-1/2,tab, color="green")
+ vert(max+1/2,tab, color="green")
+ vert(i+1/2, tab, color="red")
)
#########################################################
yield "Start", plot_tab(T)
min = 0
max = len(T)-1
while (min < max):
# Invariant les éléments d'indice < min ou > max sont à leurs places
# Phase montante
nborne = min
for i in range(min, max): # min, min+1, ..., max-1
yield dessin()
if (T[i] > T[i+1]):
T[i], T[i+1] = T[i+1], T[i]
nborne = i
max = nborne
# Phase descendante
nborne = max
for i in range(max-1, min-1, -1): # max-1, max-2, ..., min
yield dessin()
if (T[i] > T[i+1]):
T[i], T[i+1] = T[i+1], T[i]
nborne = i + 1
min = nborne
yield dessin()
tab = [randint(0, 100) for i in range(10)]
trace_algo(bubble_sort_2d(tab))
def insert_sort(T):
#########################################################
## dessin qui va être affiché lors des points d'arrêt ###
## vous pouvez complètement ingorer ce code.
def dessin():
return ("i=%i, j=%i, e=%i"%(i,j,e),
plot_tab(T)+vert(j, tab)+horiz(e, tab))
#########################################################
yield "Start", plot_tab(T)
for i in range(1,len(T)):
e = T[i]
j = i
yield dessin()
while j>0 and T[j-1] > e:
T[j] = T[j-1]
j -= 1
yield dessin()
T[j] = e
yield dessin()
tab = [randint(0, 40) for i in range(10)]
trace_algo(insert_sort(tab))
tab
def partition(Tab, P):
c = 0; j = 0
#########################################################
## dessin qui va être affiché lors des points d'arrêt ###
## vous pouvez complètement ingorer ce code.
def dessin():
return (sum(point((i,v), size=SIZE_POINT,
color="green" if P(v) else "red")
for i,v in enumerate(tab))
+ vert(c, Tab, color="green") + vert(j, Tab))
#########################################################
yield "Start", dessin()
c = 0
while c < len(Tab) and P(Tab[c]):
c +=1
yield "c=%i"%c, dessin()+vert(c,Tab,color= "green")
for j in range(c+1, len(Tab)):
yield ("c=%i, j=%i"%(c, j), dessin())
if P(Tab[j]):
Tab[c], Tab[j] = Tab[j], Tab[c]
c +=1
yield ("c=%i, j=%i"%(c, j), dessin())
yield ("Retour %i"%c,
dessin()+vert(c-1/2, Tab, color="blue"))
tab = [randint(0, 20) for i in range(20)]
trace_algo(partition(tab, lambda x: x % 2 == 0))
Interactive function <function trace_algo.<locals>.bla at 0x7fe31d6682f0> with 1 widget cmd: ToggleButtons(d…
def partition2(Tab, P):
#########################################################
## dessin qui va être affiché lors des points d'arrêt ###
## vous pouvez complètement ingorer ce code.
def dessin():
return (sum(point((i,v), size=SIZE_POINT,
color="green" if P(v) else "red")
for i,v in enumerate(tab))
+ vert(i, Tab, color="green")
+ vert(j, Tab, color="red"))
#########################################################
i = 0
j = len(Tab)-1
yield "Start", dessin()
while i <= j:
while P(Tab[i]): i += 1
while not P(Tab[j]): j -= 1
yield "i=%i, j=%i"%(i, j), dessin()
if i<j:
Tab[i], Tab[j] = Tab[j], Tab[i]
yield "i=%i, j=%i"%(i, j), dessin()
i += 1; j -= 1
yield ("Retour %i"%(i),
dessin() + vert(i-1/2, Tab, color="blue"))
tab = [randint(0, 20) for i in range(20)]
trace_algo(partition2(tab, lambda x: x % 3 == 0))
Interactive function <function trace_algo.<locals>.bla at 0x7fe31cd07ae8> with 1 widget cmd: ToggleButtons(d…
def quicksort(tab, min, max):
#########################################################
## dessin qui va être affiché lors des points d'arrêt ###
## vous pouvez complètement ingorer ce code.
def dessin():
return(
"min = %i, max=%i, pivot=%i, i=%i, j=%i"%(
min, max, pivot, i, j),
sum(point((pos,v), size=SIZE_POINT,
color =
"blue" if pos < min or pos > max
else
"red" if v > pivot
else
"green")
for pos,v in enumerate(tab))
+ vert(i, tab, color="black")
# + vert(j, tab, color="blue")
+ vert(min, tab, color="blue")
+ vert(max, tab, color="blue")
+ horiz(pivot, tab))
#########################################################
if min < max:
pivot = tab[max]
# Partitionnement
i = min
j = max-1
yield dessin()
while True:
while tab[i] < pivot: i +=1
while tab[j] > pivot: j -=1
if i < j:
tab[i], tab[j] = tab[j], tab[i]
i += 1; j -= 1
else:
tab[i], tab[max] = tab[max], tab[i]
break
# Appel récursif
yield dessin()
for step in quicksort(tab, min, i-1):
yield step
for step in quicksort(tab, i+1, max):
yield step
tab = [randint(0, 20) for i in range(15)]
print(tab)
for step in quicksort(tab, 0, len(tab)-1):
pass
tab
[0, 17, 4, 13, 19, 15, 0, 12, 9, 20, 16, 19, 19, 5, 3]
[0, 0, 3, 4, 5, 9, 12, 13, 15, 16, 17, 19, 19, 19, 20]
tab = [randint(0, 20) for i in range(20)]
trace_algo(quicksort(tab, 0, len(tab)-1))
Interactive function <function trace_algo.<locals>.bla at 0x7fe31d47c400> with 1 widget cmd: ToggleButtons(d…