[Edu-sig] Analyzing algorithms...
Dr. David J. Ritchie, Sr.
djrassoc01@mindspring.com
Mon, 25 Feb 2002 09:45:38 -0600
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/