{{{id=18|
def trace_algo(cmd):
sort_gen = iter(cmd)
def bla(cmd=selector(["Step"],
buttons=True)):
global dessin
try:
mess, dessin = sort_gen.next()
except StopIteration:
mess = "======== Finished ======="
print mess
dessin.show(figsize=(7,4))
interact(bla)
///
}}}
{{{id=23|
def plot_tab(tab):
return sum(point(v, size=50) 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)
///
}}}
{{{id=28|
///
}}}
Bubble Sort
{{{id=3|
def bubble_sort(T):
def dessin():
return ("i=%i, j=%i"%(i,j),
sum(point((pos,v), size=50,
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)
for i in range(len(T)-1, 0, -1):
for j in range(i):
yield dessin()
if T[j] > T[j+1]:
T[j], T[j+1] = T[j+1], T[j]
yield dessin()
///
}}}
{{{id=20|
tab = [randint(0, 20) for i in range(10)]
trace_algo(bubble_sort(tab))
///
}}}
{{{id=46|
def bubble_sort_2d(T):
def dessin():
return ("i=%i, min=%i, max=%i"%(i,min,max),
sum(point((pos,v), size=50,
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):
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):
yield dessin()
if (T[i] > T[i+1]):
T[i], T[i+1] = T[i+1], T[i]
nborne = i
min = nborne+1
///
}}}
{{{id=47|
tab = [randint(0, 100) for i in range(20)]
trace_algo(bubble_sort_2d(tab))
///
}}}
Insert Sort
{{{id=7|
def insert_sort(T):
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()
///
}}}
{{{id=19|
tab = [randint(0, 20) for i in range(10)]
trace_algo(insert_sort(tab))
///
}}}
Partitioning
Left to right method
{{{id=6|
def partition(Tab, P):
c = 0; j = 0
def dessin():
return (sum(point((i,v), size=40,
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"))
///
}}}
{{{id=8|
tab = [randint(0, 20) for i in range(20)]
trace_algo(partition(tab, lambda x: x % 2 == 0))
///
}}}
{{{id=33|
///
}}}
Double sided method
{{{id=4|
def partition2(Tab, P):
def dessin():
return (sum(point((i,v), size=40,
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