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
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?
I'd probably make the elements to be sorted instances of some object, override the comparison operators, and build a counter into their invocation. Something similar could be done with assignment, where you use an object method to store an element, versus a simple =. E.g.:
class Element: def __init__(self,val): self.value = val self.comp = 0
def __repr__(self): return str(self.value) def __eq__(self,other): self.comp += 1 other.comp += 1 return self.value==other.value def __gt__(self,other): self.comp += 1 other.comp += 1 return self.value>other.value def __lt__(self,other): self.comp += 1 other.comp += 1 return self.value<other.value def __le__(self,other): self.comp += 1 other.comp += 1 return self.value<=other.value def __ge__(self,other): self.comp += 1 other.comp += 1 return self.value>=other.value
a = Element(1) b = Element(2) a<b 1 a==b 0 a>=b 0 a<=b 1 a>b 0 a.comp # internal counter knows how many comparisons 5 b.comp # ditto
Kirby
Wow! Two very helpful replies within two hours on a Sunday afternoon. This list rocks! Thanks Kirby and Tim, I'm all set. jeff
Jeffrey Elkner <jeff@elkner.net>:
Wow! Two very helpful replies within two hours on a Sunday afternoon.
This list rocks!
Thanks Kirby and Tim, I'm all set.
jeff
Sorry, I'm late, but I'll add a link here to one of the many sites doing animated algorithms which I find even more impressive than creating lists of counters: http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html I used to know some cool demo comparing various sorting algorithms simultaneously in the same fashion on the former NeXTSTEP system, but I was not able to find that quickly on the net... Regards, Dinu
Hi Kirby, With the help of student Python guru, Lex Berezhny, I've been playing around a bit with the suggestion you sent me. Here is what I get when I attempt to merge the "Element" class you sent me with a "countable thing" class that Lex showed me: class COUNTER: stat_state = {} def __init__(self, value = 0, type): self.value = value if not self.stat_state.has_key(type): self.stat_state[type] = stat_state = {"assign": 0, "compare": 0} self.stat = self.stat_state[type] def __repr__(self): return str(self.value) def __eq__(self, other): self.state["compare"] += 1 return self.value == other.value def __gt__(self, other): self.state["compare"] += 1 return self.value > other.value def __lt__(self, other): self.state["compare"] += 1 return self.value < other.value def __le__(self, other): self.state["compare"] += 1 return self.value <= other.value def __ge__(self, other): self.state["compare"] += 1 return self.value >= other.value The idea is to create a class of things that know how to count together, so that they increment a common counter (so a > b should only count 1 comparison). I couldn't find a way to give this property to assignment. Every time an assignment happens with one of these things, I would like to count it. Is there a way to do that? jeff
I couldn't find a way to give this property to assignment. Every time an assignment happens with one of these things, I would like to count it. Is there a way to do that?
jeff
Trickier I think, because unlike <, > etc., = doesn't trigger some __xxx__ method. But sticking something in a property or explicitly invoking a method could work. If you're willing to do something like: b.assign(a) or b.value = a in place of b = a then we'd have some options. But that might detract from the readibility of your sort algorithms, as there's nothing more natural than plain old =. So maybe we fall back to triggering an assignment counter each time there's an assignment, e.g. pepper the code like: a = b a.assign() # not sure if you count one or both That's not much better than sticking in accumulator variables, but perhaps keeps things clearner in that you're still using the elements to be sorted to keep track of their own manipulations. Kirby
On 27 Feb 2002, Jeffrey Elkner wrote:
I couldn't find a way to give this property to assignment. Every time an assignment happens with one of these things, I would like to count it. Is there a way to do that?
I would guess that assignments you're interested in don't have the form a = 2 * x + 15 but rather have the form array[i] = 2 * x + 15 because scalar variables like 'a' are seldom significant in the analysis of a program, while arrays are. If, then, you attached an "assign" counter to array objects' __setitem__ functions, I think you'd be in business.. Dustin -- Dustin Mitchell dustin@cs.uchicago.edu dustin@ywlcs.org http://people.cs.uchicago.edu/~dustin/
Hey Jeff -- Thanks to a fast-enough internet connection, I was able to grab and view your school's funky 243 MB mpg video re Python. Great to see you and other members of the cast -- Tim Peters, Guido et al. I'll burn this to a CD and maybe share it with a high schooler or two. Lots of video skills being demoed here too. I like your high tech curriculum. Kirby URL for video and many other interesting presentations at the most recent Python conference: http://www.python.org/workshops/2002-02/
[Jeffrey Elkner]
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?
That's what I usually do, but recently a semi-maddening semi-wonderful alternative became available via Tools/scripts/trace.py (in your Python distribution). The maddening part is that it's almost impossible to figure out how to use it: the docs (consisting of a --help message) talk about many options, but there's no overview, and no explantion of what the (non-option) arguments are supposed to be. So here's just-about simplest-possible use explained via example. Here's a file with a poor sort function: C:\Python22>type bubblesort.py def bubble(a): n = len(a) changed = 1 while changed: changed = 0 for i in xrange(n-1): if a[i] > a[i+1]: a[i], a[i+1] = a[i+1], a[i] changed = 1 n -= 1 import random a = range(20) random.shuffle(a) print a bubble(a) print a Now I run it, just to make sure it works: C:\Python22>python bubblesort.py [14, 9, 7, 5, 16, 13, 1, 10, 17, 3, 11, 19, 0, 18, 8, 2, 12, 4, 6, 15] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] Now pass the file to trace.py with the "-c" option: C:\Python22>python Tools/scripts/trace.py -c bubblesort.py [8, 12, 0, 6, 11, 16, 4, 17, 7, 10, 18, 2, 1, 9, 15, 19, 13, 5, 3, 14] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] That took much longer to run, but it's worth it because of what happens next: it left behind a text file named bubblsort.cover, which *annotates* each source line with the number of times it was executed: C:\Python22>type bubblesort.cover 2: def bubble(a): 2: n = len(a) 1: changed = 1 18: while changed: 16: changed = 0 216: for i in xrange(n-1): 184: if a[i] > a[i+1]: 87: a[i], a[i+1] = a[i+1], a[i] 87: changed = 1 16: n -= 1 . 1: import random 1: a = range(20) 1: random.shuffle(a) 1: print a 1: bubble(a) 1: print a . C:\Python22> It *also* left behind a random.cover file in the Lib directory. Stopping (possibly) unwanted stuff like that is what some of the other options aim at. Note some odd things about the output; in typical use they don't really matter, but if you're after exact counts you have to be aware of them: What trace.py actually counts is the number of SET_LINENO opcodes executed. Because "def" is an executable statement in Python, the count on "def bubble(a)" is actually two: it gets counted once for the time the def statement is executed (which defines the function), and a second time for *calling* the "bubble" function. I can't account for why the count is also two on "n = lan(a)"; looks like a bug. The count on "while 1" is 1 larger than "it should be", because under the covers a special SETUP_LOOP opcode is generated to get the while-loop started, and is executed one per function call. It gets counted against the "while changed:" line because the closest preceding SET_LINENO opcode said the SETUP_LOOP is due to line #4 in the function. The count on the "for" loop is also too large for the same reason, but worse because its hidden SETUP_LOOP opcode is executed (and counted against the "for") once for each iteration of the outer while-loop. As a result, the count on "for" is 16 la rger than expected (it *should* be 16 larger than the count on "if a[i] > ...", not 32 larger). The counts on the "plain old lines" within the loops are on the nose, though, and that's what's really important. Good luck!
""" 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
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/
In my opinion it is not feasible to measure or even estimate the runtime- behaviour of those algorithms from the demos. They use different time-constants for the animation: 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) Moreover most of the time is consumed by displaying the graphics and it is questionable if the time consumed by those canvas.update()-calls is proportional to the time of the not animated sorts. Gregor ----- Original Message ----- From: "Kirby Urner" <urnerk@qwest.net> To: <edu-sig@python.org> Sent: Monday, February 25, 2002 5:52 PM Subject: Re: [Edu-sig] Analyzing algorithms...
Judging purely from the demos, insertion-sort seemed fastest.
Kirby
_______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
At 06:21 PM 2/25/2002 +0100, Gregor Lingl wrote:
In my opinion it is not feasible to measure or even estimate the runtime- behaviour of those algorithms from the demos.
Yeah, that sounds reasonable. The point of the animations is to give some idea of how they work, not which is ultimately fastest. A caveat to share with students if using them in a classroom setting. Kirby
In regard to what Kirby Urner wrote:
At 06:21 PM 2/25/2002 +0100, Gregor Lingl wrote:
In my opinion it is not feasible to measure or even estimate the runtime- behaviour of those algorithms from the demos.
Yeah, that sounds reasonable. The point of the animations is to give some idea of how they work, not which is ultimately fastest. A caveat to share with students if using them in a classroom setting.
Yes. I used it as part of our 50 minute computer club today for seven students in sixth-eighth grades and it provided a good example of different sorting techniques. Thank you very much to those who authored and contributed it. --David -- Dr. David J. Ritchie, Sr. djrassoc01@mindspring.com http://home.mindspring.com/~djrassoc01/
Jeffrey Elkner wrote:
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!
This is a very late contribution, but as I'm going through some of the hidden corners of my mailbox I might be able to add a comment, if you permit? I *think* sorting algorithms are compared using the number of compare and swap operations, so I assume by counting assign- ments you actually meant swap operations, isn't it? If so I believe the issue can be solved in the good old OO-way by creating an abstract sorting base class with concrete sub- classes of it. My preference would something like this (with visualising calls commented): --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- class Sorter: """An abstract sorting class. This contains hooks for swapping and comparing elements to be implemented in subclasses. Other methods could be filled in for visualising the algorithm used (and/or be called on respective delegates). """ def __init__(self): self.cmpCount = 0 self.swapCount = 0 def __call__(self, aList=None): self.sort(aList) def swap(self, aList, i, j): self.swapCount = self.swapCount + 1 L = aList L[i],L[j] = L[j],L[i] def compare(self, aList, i, j): self.cmpCount = self.cmpCount + 1 L = aList return cmp(L[i], L[j]) def sort(self, aList): raise "NotImplemented" class BubbleSort(Sorter): def sort(self, aList): L = aList # 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 self.compare(L, z, z+1) >= 0: self.swap(L, z, z+1) # SHOW_zeig([z, z+1]) bs = BubbleSort() print bs.__class__.__name__ L = [9, 5, 2, 7, 6, 1, 3] print L bs(L) print L args = (bs. cmpCount, bs.swapCount) print "compares: %d, swaps: %d" % args --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- With some slight modifications you can plug this directly into the code posted by Gregor Lingl, replacing the bubble function with the following code like this: --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- class Sorter: def __init__(self, aList=None): self.cmpCount = 0 self.swapCount = 0 return self(aList) def __call__(self, aList=None): return self.sort(aList) def swap(self, aList, a, b): self.swapCount = self.swapCount + 1 L = aList L[a],L[b] = L[b],L[a] def compare(self, aList, a, b): self.cmpCount = self.cmpCount + 1 L = aList return cmp(L[a], L[b]) def sort(self, aList): return aList ############################################################## ## BubbleSort und Verwandte class bubble(Sorter): def sort(self, aList=None): 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 self.compare(L, z, z+1) >= 0: self.swap(L,z,z+1) SHOW_zeig([z,z+1]) --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- Jeff, does this also solve your problem, or is anything fun- damentally wrong with it? At least you don't have to implement many double underscore methods... Of course, I know more recent Python versions have function attributes, but then, strictly speaking, they aren't func- tions any more. Regards, Dinu -- Dinu C. Gherman ................................................................ "The world becomes a better place as a result of the refusal to bend to authority and doctrine." (Noam Chomsky)
participants (7)
-
Dinu Gherman -
Dr. David J. Ritchie, Sr. -
Dustin Mitchell -
Gregor Lingl -
Jeffrey Elkner -
Kirby Urner -
Tim Peters