Re: [Edu-sig] Analyzing algorithms...

25 Feb 2002

      In regard to what Gregor Lingl wrote:
...
"""
A friend of mine wrote a program not to analyze but
to visualize different sorting algorithms. It's
shown below.
....
...
Run it.
Maybe you enjoy it.
Yes, it is very nice.  Ran fine on a Mac under Python 2.1
with the Tkinter (and Python) that comes on the
"Learning Python" book CD.

At the end of the first sort (Bubble Sort) as run by the
demo which is selected when the program is run
with no arguments, I got a "handle already in use"
(or some such thing) error.

So, enclosed is a slightly revised version with things
moved around to avoid that and which displays each
sort in the demo in a different Toplevel window.

Now, if someone wants to multi-thread the demo's
so they show the sorts in the separate top level windows
going on all simultaneous...

==================================

## Wolfgang.Urban@schule.at 02/2002
## animierte Sortierung
## grün: aktueller Bereich in Arbeit
## rot: momentan beartbeitete Elemente
## mit commandline

## djrassoc01@mindspring.com 02/25/2002
## each sort in its own separate toplevel window in demo
## no error after first demo sort.
## Have not tested non-null command line operation

import random
import time
import string
from Tkinter import *
import sys

##############################################################
## Hilfsfunktionen
##############################################################

## range() mit inkludiertem letztem Wert
def fullrange(a,b,step=1):
    if step>0: return range(a,b+1,step)
    else: return range(a,b-1,step)

## vertauscht zwei Listenelemente
def swap(L,a,b):
    L[a],L[b] = L[b],L[a]

###################################################################
## Listen mit jeweils n Elemnenten zum Testen zur Verfügung stellen
## korrekt : bereits sortiert
## verkehrt: gestürzt
## konstant: lauter gleiche Werte
## dazu    : richtig sortiert, aber letzte 'neu' Werte wiederum klein
###################################################################
def listen(): return['korrekt','verkehrt','konstant','zufall','dazu']

def korrekt(n=10):
    return fullrange(1,n)

def verkehrt(n=10):
    return fullrange(n,1,-1)

def konstant(n=10):
    return [n/2]*n

def zufall(n=10):
    liste = n*[0]
    for x in range(n):
        liste[x]=random.randrange(1,n+1)
    return liste

def dazu(n=10,neu=3):
    return fullrange(1,n-neu)+fullrange(1,neu)

##############################################################
## die Sortieralgorithmen
##############################################################

def methoden():
    return ['bubble','bubbleclever','shaker','insertion','selection',\
            'shell','quick','heap','merge']

##############################################################
## BubbleSort und Verwandte

def bubble():
    global L
    SHOW_bereich_quickest(0,len(L)-1)
    for x in range(len(L)):
        for z in fullrange(0,len(L)-2):
            SHOW_element1(z)
            SHOW_element2(z+1)
            if L[z]>L[z+1]:
                swap(L,z,z+1)
                SHOW_zeig([z,z+1])

def bubbleclever():
    global L
    for oben in fullrange(len(L)-1,1,-1):
        SHOW_bereich_quickest(0,oben)
        for z in fullrange(0,oben-1):
            if L[z]>L[z+1]:
                SHOW_element1(z)
                SHOW_element2(z+1)
                swap(L,z,z+1)
                SHOW_zeig([z,z+1])

def shaker():
    global L
    TRUE = 1
    FALSE = 0
    erstes = 0
    letztes = len(L)-1
    while TRUE:

        fertig = TRUE
        SHOW_bereich_quick(erstes,letztes)
        for i in fullrange(erstes,letztes-1):
            SHOW_element1(i)
            SHOW_element2(i+1)
            if L[i]>L[i+1]:
                swap(L,i,i+1)
                SHOW_zeig([i,i+1])
                fertig = FALSE
        letztes = letztes-1
        if fertig: return

        fertig = TRUE
        SHOW_bereich_quick(erstes,letztes)
        for i in fullrange(letztes,erstes+1,-1):
            SHOW_element1(i-1)
            SHOW_element2(i)
            if L[i-1]>L[i]:
                swap(L,i-1,i)
                SHOW_zeig([i-1,i])
                fertig = FALSE
        erstes = erstes+1
        if fertig: return

##############################################################
## Insertion Sort

def insertion():
    global L
    for stelle in range(1,len(L)):
        wert = L[stelle]
        i = stelle
        SHOW_element1(stelle)
        SHOW_bereich_quickest(0,stelle)
        while 1:
            SHOW_element1(i-1)
            if i==0: break
            if L[i-1]<=wert: break
            L[i] = L[i-1]
            # SHOW_bereich_quickest(i,stelle)
            SHOW_zeig([i,i-1])
            i = i-1
        L[i] = wert
        SHOW_zeig([stelle,i])

##############################################################
## Selection Sort

def selection():
    global L
    for start in fullrange(0,len(L)-2):
        z = start
        SHOW_element1(start)
        SHOW_bereich(start,len(L)-1)
        for i in fullrange(start+1,len(L)-1):
            SHOW_element2(i)
            if L[i]<L[z]:
                z=i
        if z != start:
            swap(L,start,z)
            SHOW_zeig([start,z])

##############################################################
## Shell Sort
def shell():
    global L
    step=1
    while step<len(L):
        step=3*step+1

    while step>1:
        step = step/3
        for i in fullrange(step,len(L)-1):
            wert = L[i]
            stelle = i
            SHOW_bereich_quick(0,stelle)
            SHOW_element1(i)
            while 1:
                if stelle<step: break
                if L[stelle-step]<=wert: break
                L[stelle] = L[stelle-step]
                SHOW_element2(stelle-step)
                SHOW_zeig([stelle,stelle-step])
                stelle = stelle-step
            L[stelle] = wert
            SHOW_zeig([stelle,i])

##############################################################
## Quick Sort

def quicksort(L,anfang,ende):
    if anfang<ende:
       p = partition(L,anfang,ende)
       quicksort(L,anfang,p-1)
       quicksort(L,p+1,ende)

def partition(L,von,bis):
    SHOW_bereich(von,bis)
    pivot = L[bis]
    i = von-1
    for j in fullrange(von,bis-1):
        if L[j]<=pivot:
           i = i+1
           swap(L,i,j)
           SHOW_zeig([i,j])
           SHOW_element1(i)
           SHOW_element2(j)

    swap(L,i+1,bis)
    SHOW_zeig([i+1,bis])
    return i+1

def quick():
    global L
    quicksort(L,0,len(L)-1)         # Startaufruf mit den Grenzen

##############################################################
## Heap Sort

def heap():
    global L
    erzeugeHeap(L)
    for letzt in fullrange(len(L)-1,1,-1):
        swap(L,0,letzt)
        SHOW_zeig([0,letzt])
        repariere(L,0,letzt-1)

def repariere(L,pos,letzt):
    SHOW_bereich_quick(pos,letzt)
    l = 2*pos+1                         # linkes Kind
    r = l+1                             # rechtes Kind
    if (l<=letzt) and (L[l]>L[pos]):
       maximal = l
    else:
       maximal = pos
    if (r<=letzt) and (L[r]>L[maximal]):
       maximal = r
    if maximal != pos:
        swap(L,maximal,pos)
        SHOW_zeig([maximal,pos])
        SHOW_element1(maximal)
        SHOW_element2(pos)
        repariere(L,maximal,letzt)

def erzeugeHeap(L):
    letzt = len(L)-1
    SHOW_bereich(0,letzt)
    for i in fullrange(len(L)/2,0,-1):
        repariere(L,i,letzt)

##############################################################
## Merge Sort

def merge():
    global L
    mergesort(L,L[:],0,len(L)-1)

def mergesort(L,H,links,rechts):
    if links<rechts:
        SHOW_bereich(links,rechts)
        mitte = (rechts+links)/2
        mergesort(L,H,links,mitte)
        mergesort(L,H,mitte+1,rechts)

        SHOW_bereich(links,rechts)
        for i in fullrange(mitte,0,-1):
            H[i]=L[i]
        for i in fullrange(mitte+1,rechts):
            H[(mitte+1)+rechts-i]=L[i]

        l = links
        r = rechts
        for i in fullrange(links,rechts):
            if H[l]<H[r]:
                L[i]=H[l]
                l = l+1
            else:
                L[i]=H[r]
                r = r-1
            SHOW_zeig([i])
            SHOW_element1(i)

################################################################
################################################################
## Grafikroutinen
################################################################
################################################################

w0 = 580        # Hauptfenster width
h0 = 330        # Hauptfenster height
scalex = 8
spacex = 3
scaley = 4
offsetx = 22    # von liks
offsety = 320   # bottom line
anzahl = 70     # Listenelemente

delay = 10      # Delay in 'zeig'

def die(event=0): sys.exit(0)

#########################################################
## kleine Anzeigeroutinen für Elemente, Bereiche, Indizes

# zeigt L[i] durch Koordinatenkorrektur an
def SHOW_zeig(obj):
    global cv,L,objNr
    for i in obj:
        x = offsetx+i*scalex
        y = offsety-L[i]*scaley
        cv.coords(objNr[i],x,y,x+scalex-spacex,offsety)
    cv.after(delay)
    cv.update()

def SHOW_bereich(i,j):
    global cv,bereich
    x1 = offsetx+i*scalex
    x2 = offsetx+(j+1)*scalex-spacex
    cv.coords(bereich,x1,offsety+5,x2,offsety+8)
    cv.after(delay*4)
    cv.update()

def SHOW_bereich_quick(i,j):
    global cv,bereich
    x1 = offsetx+i*scalex
    x2 = offsetx+(j+1)*scalex-spacex
    cv.coords(bereich,x1,offsety+5,x2,offsety+8)
    cv.after(delay/2)
    cv.update()

def SHOW_bereich_quickest(i,j):
    global cv,bereich
    x1 = offsetx+i*scalex
    x2 = offsetx+(j+1)*scalex-spacex
    cv.coords(bereich,x1,offsety+5,x2,offsety+8)
    # cv.after(delay/2)
    cv.update()

def SHOW_element1(i):
    global cv,punkt1
    x1 = offsetx+i*scalex
    cv.coords(punkt1,x1,offsety+1,x1+scalex-1,offsety+4)

def SHOW_element2(i):
    global cv,delay,punkt2
    x1 = offsetx+i*scalex
    cv.coords(punkt2,x1,offsety+1,x1+scalex-1,offsety+4)
    cv.after(delay/4)
    cv.update()

# zeigt gesamte Liste
def SHOW_zeigalles():
    global L
    SHOW_zeig(range(len(L)))

# erzeugt Rechteck für L[i]
def mach(i):
    global cv,L,objNr
    x = offsetx+i*scalex
    y = offsety-L[i]*scaley
#    color=hex(16+L[i]*3)
#    f = "#"+color[2:]+"0000"
#    objNr[i]=cv.create_rectangle(x,y,x+scalex-spacex,offsety,fill=f)
    objNr[i]=cv.create_rectangle(x,y,x+scalex-spacex,offsety)

# erzeugt alle Rechtecke für L
def machalles():
    global L,bereich,punkt1,punkt2
    for i in range(len(L)): mach(i)
    bereich = cv.create_rectangle(0,0,2,2,fill="#00ff00")
    punkt1 = cv.create_rectangle(0,0,2,2,fill="#ff0000")
    punkt2 = cv.create_rectangle(0,0,2,2,fill="#ff0000")

#######################################################
## Beschriftung und Canvas erzeugen, Routine ausführen,
## Widgets (quick and very dirty) am Schluss vernichten

def doit(wmeth, name,deltime):
    global root,cv,L,objNr,delay,bereich,punkt1,punkt2

    label=Label(wmeth,text=string.upper(name+'-sort'),
          font=(('Arial'),'12'),borderwidth=10).pack(side=TOP)
    cv = Canvas(wmeth,width=w0,height=h0,borderwidth=10,
                background="#b0b0b0")
    wmeth.bind("<Escape>",die)
    cv.pack(expand=1,fill=NONE)
    cv.create_rectangle(offsetx-1,offsety,

offsetx+anzahl*scalex-spacex+1,offsety-(anzahl+1)*scaley-1,
                        fill="#d0d0d0", outline="#d0d0d0")
    L = zufall(anzahl)
    objNr = L[:]

    delay = deltime
    machalles()
    SHOW_zeigalles()
    cv.after(1500)
    cv.update()
    eval(name)()
    cv.coords(bereich,0,0,0,0)
    cv.coords(punkt1,0,0,0,0)
    cv.coords(punkt2,0,0,0,0)
    cv.update()

####################
## automatische Demo

def do_demo(meth,deltime):
    global root
    wmeth = Toplevel(root)
    wmeth.title("Animierte Sortieralgorithmen: " + meth)
    doit(wmeth, meth, deltime)
    root.after(1000)
    root.update()
    wmeth.destroy()

def demo():
    do_demo('bubble',5)
    do_demo('bubbleclever ',11)
    do_demo('shaker',15)
    do_demo('selection ',22)
    do_demo('insertion ',4)
    do_demo('shell',25)
    do_demo('quick',50)
    do_demo('heap',28)
    do_demo('merge',22)

##############################################
## Startroutine mit Übergabe von Kommandozeile
def start():
    global root
    root = Tk()
    cmdline = sys.argv[1:]
    meth=""
    if cmdline==[]:
        demo()
        return
    else:
        for r in methoden():
            if string.upper(r)==string.upper(cmdline[0]):
                meth=r
                break
        if meth=='':
            print "Algorithmus",cmdline[0],"unbekannt."
            sys.exit(1)
        deltime=15
        if len(cmdline)>1: deltime=int(cmdline[1])

    wmeth = Toplevel(root)

    wmeth.title("Animierte Sortieralgorithmen:" + meth)
    doit(wmeth, meth, deltime)

    root.after(1000)
    root.update()
    wmeth.destroy()
    root.mainloop()

######################################################################

start()

========================
--
Dr. David J. Ritchie, Sr.
djrassoc01@mindspring.com
http://home.mindspring.com/~djrassoc01/