3627-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 = "======== Finished ======="
        print mess
        dessin.show(figsize=(8,6))
    interact(bla)

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)

Bubble Sort

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):
            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)]
trace_algo(bubble_sort(tab))

cmd  [removed] [removed] [removed] [removed]

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)]
trace_algo(insert_sort(tab))

cmd  [removed] [removed] [removed] [removed]

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, 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)]
tab = [1]+[2]*15
trace_algo(partition(tab, lambda x: x % 2 == 0))

cmd  [removed] [removed] [removed] [removed]

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

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

cmd  [removed] [removed] [removed] [removed]

Quick Sort

def quicksort(tab, min, max):
    
    def dessin():
        return(
           "min = %i, max=%i, pivot=%i, i=%i, j=%i"%(
                min, max, pivot, i, j),
            sum(point((pos,v), size=40, 
                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]
        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
        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

[9, 1, 2, 0, 8, 14, 13, 13, 13, 18, 8, 19, 17, 17, 12] [0, 1, 2, 8, 8, 9, 12, 13, 13, 13, 14, 17, 17, 18, 19]

tab = [randint(0, 20) for i in range(20)]
trace_algo(quicksort(tab, 0, len(tab)-1))

cmd  [removed] [removed] [removed] [removed]