3611-Left to right method.sagews

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 = "======== Fin ======="
        print mess
        dessin.show()
    return (bla)

def plot_tab(tab):
    return sum(point(v, size=50) for v in
                enumerate(tab))

def vert(i, tab, color="red"):
    return line([(i, 0),(i, max(tab))], color=color)

def horiz(i, tab, color="green"):
    return line([(0,i),(len(tab),i)], color=color)

Bubble Sort

def bubble_sort(T):
    def dessin():
        return ("i=%i, j=%i"%(i,j), plot_tab(T)+
                     vert(i,tab)+vert(j+1/2,tab))
    yield "Start", plot_tab(T)
    for i in range(len(T)-1, 0, -1):
        for j in range(i):
            if T[j] > T[j+1]:
                T[j], T[j+1] = T[j+1], T[j]  
            yield dessin()

tab = [randint(0, 20) for i in range(10)]
interact(trace_algo(bubble_sort(tab)))

Insert Sort

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()

tab = [randint(0, 20) for i in range(10)]
interact(trace_algo(insert_sort(tab)))

Partitioning

Left to right method

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, "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, "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, "blue"))

tab = [randint(0, 20) for i in range(20)]
interact(trace_algo(partition(tab, 
                      lambda x: x % 2 == 0)))

cmd  Step

<function bla at 0x570bd70>

Double sided method

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, "green") + vert(j, Tab))
            
    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-1), 
            dessin() + vert(i-1/2, Tab, "blue"))

tab = [randint(0, 20) for i in range(20)]
interact(trace_algo(partition2(tab, 
                      lambda x: x % 2 == 0)))

cmd  Step

<function bla at 0x6498a28>