[Edu-sig] Analyzing algorithms...
Gregor Lingl
glingl@aon.at
Mon, 25 Feb 2002 08:43:06 +0100
"""
A friend of mine wrote a program not to analyze but
to visualize different sorting algorithms. It's
shown below.
So it's a different topic, nevertheless I think
it's interesting for educational purposes and fits
into this context.
(And there is a similar problem to that you mentioned
(with displaying instead of counting), which perhaps
could be solved in a better way than it is done below.)
Run it.
Maybe you enjoy it.
Gregor
"""
## Wolfgang.Urban@schule.at 02/2002
## animierte Sortierung
## grün: aktueller Bereich in Arbeit
## rot: momentan beartbeitete Elemente
## mit commandline
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(name,deltime):
global root,cv,L,objNr,delay,bereich,punkt1,punkt2
label=Label(root,text=string.upper(name+'-sort'),
font=(('Arial'),'12'),borderwidth=10).pack(side=TOP)
cv = Canvas(root,width=w0,height=h0,borderwidth=10,
background="#b0b0b0")
root.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
root = Tk()
root.title("Animierte Sortieralgorithmen")
doit(meth,deltime)
root.after(1000)
root.update()
root.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
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])
root = Tk()
root.title("Animierte Sortieralgorithmen")
doit(meth,deltime)
root.after(1000)
root.update()
root.destroy()
root.mainloop()
######################################################################
start()
----- Original Message -----
From: "Jeffrey Elkner" <jeff@elkner.net>
To: <edu-sig@python.org>
Sent: Sunday, February 24, 2002 9:53 PM
Subject: [Edu-sig] Analyzing algorithms...
> After attending Pai Chou's wonderful presentation, "Algorithm Education
> in Python" at Python10, I got permission from the instructor of an
> algorithms course I am currently taking to do our programming
> assignments in Python (after first assuring him that they would not be
> difficult to read ;-)
>
> Our first assignment is to implement merge and heap sort and then to
> compare them empirically as to the number of assignments and comparisons
> made by each.
>
> I've written the sorts. Does anyone have any suggestions as to the best
> way to do the empirical analysis? Is there a better way than just
> creating counters and then littering my code with increment statements?
>
> Please let me know if you have any ideas?
>
> Thanks!
>
> jeff elkner
> yorktown high school
> arlington, va
>
>
>
> _______________________________________________
> Edu-sig mailing list
> Edu-sig@python.org
> http://mail.python.org/mailman/listinfo/edu-sig
>