1 #!/usr/bin/env python3
2
3 """
4 Sorting algorithms visualizer using Tkinter.
5
6 This module is comprised of three ``components'':
7
8 - an array visualizer with methods that implement basic sorting
9 operations (compare, swap) as well as methods for ``annotating'' the
10 sorting algorithm (e.g. to show the pivot element);
11
12 - a number of sorting algorithms (currently quicksort, insertion sort,
13 selection sort and bubble sort, as well as a randomization function),
14 all using the array visualizer for its basic operations and with calls
15 to its annotation methods;
16
17 - and a ``driver'' class which can be used as a Grail applet or as a
18 stand-alone application.
19 """
20
21 from tkinter import *
22 import random
23
24 XGRID = 10
25 YGRID = 10
26 WIDTH = 6
27
28
29 class ESC[4;38;5;81mArray:
30
31 class ESC[4;38;5;81mCancelled(ESC[4;38;5;149mBaseException):
32 pass
33
34 def __init__(self, master, data=None):
35 self.master = master
36 self.frame = Frame(self.master)
37 self.frame.pack(fill=X)
38 self.label = Label(self.frame)
39 self.label.pack()
40 self.canvas = Canvas(self.frame)
41 self.canvas.pack()
42 self.report = Label(self.frame)
43 self.report.pack()
44 self.left = self.canvas.create_line(0, 0, 0, 0)
45 self.right = self.canvas.create_line(0, 0, 0, 0)
46 self.pivot = self.canvas.create_line(0, 0, 0, 0)
47 self.items = []
48 self.size = self.maxvalue = 0
49 if data:
50 self.setdata(data)
51
52 def setdata(self, data):
53 olditems = self.items
54 self.items = []
55 for item in olditems:
56 item.delete()
57 self.size = len(data)
58 self.maxvalue = max(data)
59 self.canvas.config(width=(self.size+1)*XGRID,
60 height=(self.maxvalue+1)*YGRID)
61 for i in range(self.size):
62 self.items.append(ArrayItem(self, i, data[i]))
63 self.reset("Sort demo, size %d" % self.size)
64
65 speed = "normal"
66
67 def setspeed(self, speed):
68 self.speed = speed
69
70 def destroy(self):
71 self.frame.destroy()
72
73 in_mainloop = 0
74 stop_mainloop = 0
75
76 def cancel(self):
77 self.stop_mainloop = 1
78 if self.in_mainloop:
79 self.master.quit()
80
81 def step(self):
82 if self.in_mainloop:
83 self.master.quit()
84
85 def wait(self, msecs):
86 if self.speed == "fastest":
87 msecs = 0
88 elif self.speed == "fast":
89 msecs = msecs//10
90 elif self.speed == "single-step":
91 msecs = 1000000000
92 if not self.stop_mainloop:
93 self.master.update()
94 id = self.master.after(msecs, self.master.quit)
95 self.in_mainloop = 1
96 self.master.mainloop()
97 self.master.after_cancel(id)
98 self.in_mainloop = 0
99 if self.stop_mainloop:
100 self.stop_mainloop = 0
101 self.message("Cancelled")
102 raise Array.Cancelled
103
104 def getsize(self):
105 return self.size
106
107 def show_partition(self, first, last):
108 for i in range(self.size):
109 item = self.items[i]
110 if first <= i < last:
111 self.canvas.itemconfig(item, fill='red')
112 else:
113 self.canvas.itemconfig(item, fill='orange')
114 self.hide_left_right_pivot()
115
116 def hide_partition(self):
117 for i in range(self.size):
118 item = self.items[i]
119 self.canvas.itemconfig(item, fill='red')
120 self.hide_left_right_pivot()
121
122 def show_left(self, left):
123 if not 0 <= left < self.size:
124 self.hide_left()
125 return
126 x1, y1, x2, y2 = self.items[left].position()
127 ## top, bot = HIRO
128 self.canvas.coords(self.left, (x1 - 2, 0, x1 - 2, 9999))
129 self.master.update()
130
131 def show_right(self, right):
132 if not 0 <= right < self.size:
133 self.hide_right()
134 return
135 x1, y1, x2, y2 = self.items[right].position()
136 self.canvas.coords(self.right, (x2 + 2, 0, x2 + 2, 9999))
137 self.master.update()
138
139 def hide_left_right_pivot(self):
140 self.hide_left()
141 self.hide_right()
142 self.hide_pivot()
143
144 def hide_left(self):
145 self.canvas.coords(self.left, (0, 0, 0, 0))
146
147 def hide_right(self):
148 self.canvas.coords(self.right, (0, 0, 0, 0))
149
150 def show_pivot(self, pivot):
151 x1, y1, x2, y2 = self.items[pivot].position()
152 self.canvas.coords(self.pivot, (0, y1 - 2, 9999, y1 - 2))
153
154 def hide_pivot(self):
155 self.canvas.coords(self.pivot, (0, 0, 0, 0))
156
157 def swap(self, i, j):
158 if i == j: return
159 self.countswap()
160 item = self.items[i]
161 other = self.items[j]
162 self.items[i], self.items[j] = other, item
163 item.swapwith(other)
164
165 def compare(self, i, j):
166 self.countcompare()
167 item = self.items[i]
168 other = self.items[j]
169 return item.compareto(other)
170
171 def reset(self, msg):
172 self.ncompares = 0
173 self.nswaps = 0
174 self.message(msg)
175 self.updatereport()
176 self.hide_partition()
177
178 def message(self, msg):
179 self.label.config(text=msg)
180
181 def countswap(self):
182 self.nswaps = self.nswaps + 1
183 self.updatereport()
184
185 def countcompare(self):
186 self.ncompares = self.ncompares + 1
187 self.updatereport()
188
189 def updatereport(self):
190 text = "%d cmps, %d swaps" % (self.ncompares, self.nswaps)
191 self.report.config(text=text)
192
193
194 class ESC[4;38;5;81mArrayItem:
195
196 def __init__(self, array, index, value):
197 self.array = array
198 self.index = index
199 self.value = value
200 self.canvas = array.canvas
201 x1, y1, x2, y2 = self.position()
202 self.item_id = array.canvas.create_rectangle(x1, y1, x2, y2,
203 fill='red', outline='black', width=1)
204 self.canvas.tag_bind(self.item_id, '<Button-1>', self.mouse_down)
205 self.canvas.tag_bind(self.item_id, '<Button1-Motion>', self.mouse_move)
206 self.canvas.tag_bind(self.item_id, '<ButtonRelease-1>', self.mouse_up)
207
208 def delete(self):
209 item_id = self.item_id
210 self.array = None
211 self.item_id = None
212 self.canvas.delete(item_id)
213
214 def mouse_down(self, event):
215 self.lastx = event.x
216 self.lasty = event.y
217 self.origx = event.x
218 self.origy = event.y
219 self.canvas.tag_raise(self.item_id)
220
221 def mouse_move(self, event):
222 self.canvas.move(self.item_id,
223 event.x - self.lastx, event.y - self.lasty)
224 self.lastx = event.x
225 self.lasty = event.y
226
227 def mouse_up(self, event):
228 i = self.nearestindex(event.x)
229 if i >= self.array.getsize():
230 i = self.array.getsize() - 1
231 if i < 0:
232 i = 0
233 other = self.array.items[i]
234 here = self.index
235 self.array.items[here], self.array.items[i] = other, self
236 self.index = i
237 x1, y1, x2, y2 = self.position()
238 self.canvas.coords(self.item_id, (x1, y1, x2, y2))
239 other.setindex(here)
240
241 def setindex(self, index):
242 nsteps = steps(self.index, index)
243 if not nsteps: return
244 if self.array.speed == "fastest":
245 nsteps = 0
246 oldpts = self.position()
247 self.index = index
248 newpts = self.position()
249 trajectory = interpolate(oldpts, newpts, nsteps)
250 self.canvas.tag_raise(self.item_id)
251 for pts in trajectory:
252 self.canvas.coords(self.item_id, pts)
253 self.array.wait(50)
254
255 def swapwith(self, other):
256 nsteps = steps(self.index, other.index)
257 if not nsteps: return
258 if self.array.speed == "fastest":
259 nsteps = 0
260 myoldpts = self.position()
261 otheroldpts = other.position()
262 self.index, other.index = other.index, self.index
263 mynewpts = self.position()
264 othernewpts = other.position()
265 myfill = self.canvas.itemcget(self.item_id, 'fill')
266 otherfill = self.canvas.itemcget(other.item_id, 'fill')
267 self.canvas.itemconfig(self.item_id, fill='green')
268 self.canvas.itemconfig(other.item_id, fill='yellow')
269 self.array.master.update()
270 if self.array.speed == "single-step":
271 self.canvas.coords(self.item_id, mynewpts)
272 self.canvas.coords(other.item_id, othernewpts)
273 self.array.master.update()
274 self.canvas.itemconfig(self.item_id, fill=myfill)
275 self.canvas.itemconfig(other.item_id, fill=otherfill)
276 self.array.wait(0)
277 return
278 mytrajectory = interpolate(myoldpts, mynewpts, nsteps)
279 othertrajectory = interpolate(otheroldpts, othernewpts, nsteps)
280 if self.value > other.value:
281 self.canvas.tag_raise(self.item_id)
282 self.canvas.tag_raise(other.item_id)
283 else:
284 self.canvas.tag_raise(other.item_id)
285 self.canvas.tag_raise(self.item_id)
286 try:
287 for i in range(len(mytrajectory)):
288 mypts = mytrajectory[i]
289 otherpts = othertrajectory[i]
290 self.canvas.coords(self.item_id, mypts)
291 self.canvas.coords(other.item_id, otherpts)
292 self.array.wait(50)
293 finally:
294 mypts = mytrajectory[-1]
295 otherpts = othertrajectory[-1]
296 self.canvas.coords(self.item_id, mypts)
297 self.canvas.coords(other.item_id, otherpts)
298 self.canvas.itemconfig(self.item_id, fill=myfill)
299 self.canvas.itemconfig(other.item_id, fill=otherfill)
300
301 def compareto(self, other):
302 myfill = self.canvas.itemcget(self.item_id, 'fill')
303 otherfill = self.canvas.itemcget(other.item_id, 'fill')
304 if self.value < other.value:
305 myflash = 'white'
306 otherflash = 'black'
307 outcome = -1
308 elif self.value > other.value:
309 myflash = 'black'
310 otherflash = 'white'
311 outcome = 1
312 else:
313 myflash = otherflash = 'grey'
314 outcome = 0
315 try:
316 self.canvas.itemconfig(self.item_id, fill=myflash)
317 self.canvas.itemconfig(other.item_id, fill=otherflash)
318 self.array.wait(500)
319 finally:
320 self.canvas.itemconfig(self.item_id, fill=myfill)
321 self.canvas.itemconfig(other.item_id, fill=otherfill)
322 return outcome
323
324 def position(self):
325 x1 = (self.index+1)*XGRID - WIDTH//2
326 x2 = x1+WIDTH
327 y2 = (self.array.maxvalue+1)*YGRID
328 y1 = y2 - (self.value)*YGRID
329 return x1, y1, x2, y2
330
331 def nearestindex(self, x):
332 return int(round(float(x)/XGRID)) - 1
333
334
335 # Subroutines that don't need an object
336
337 def steps(here, there):
338 nsteps = abs(here - there)
339 if nsteps <= 3:
340 nsteps = nsteps * 3
341 elif nsteps <= 5:
342 nsteps = nsteps * 2
343 elif nsteps > 10:
344 nsteps = 10
345 return nsteps
346
347 def interpolate(oldpts, newpts, n):
348 if len(oldpts) != len(newpts):
349 raise ValueError("can't interpolate arrays of different length")
350 pts = [0]*len(oldpts)
351 res = [tuple(oldpts)]
352 for i in range(1, n):
353 for k in range(len(pts)):
354 pts[k] = oldpts[k] + (newpts[k] - oldpts[k])*i//n
355 res.append(tuple(pts))
356 res.append(tuple(newpts))
357 return res
358
359
360 # Various (un)sorting algorithms
361
362 def uniform(array):
363 size = array.getsize()
364 array.setdata([(size+1)//2] * size)
365 array.reset("Uniform data, size %d" % size)
366
367 def distinct(array):
368 size = array.getsize()
369 array.setdata(range(1, size+1))
370 array.reset("Distinct data, size %d" % size)
371
372 def randomize(array):
373 array.reset("Randomizing")
374 n = array.getsize()
375 for i in range(n):
376 j = random.randint(0, n-1)
377 array.swap(i, j)
378 array.message("Randomized")
379
380 def insertionsort(array):
381 size = array.getsize()
382 array.reset("Insertion sort")
383 for i in range(1, size):
384 j = i-1
385 while j >= 0:
386 if array.compare(j, j+1) <= 0:
387 break
388 array.swap(j, j+1)
389 j = j-1
390 array.message("Sorted")
391
392 def selectionsort(array):
393 size = array.getsize()
394 array.reset("Selection sort")
395 try:
396 for i in range(size):
397 array.show_partition(i, size)
398 for j in range(i+1, size):
399 if array.compare(i, j) > 0:
400 array.swap(i, j)
401 array.message("Sorted")
402 finally:
403 array.hide_partition()
404
405 def bubblesort(array):
406 size = array.getsize()
407 array.reset("Bubble sort")
408 for i in range(size):
409 for j in range(1, size):
410 if array.compare(j-1, j) > 0:
411 array.swap(j-1, j)
412 array.message("Sorted")
413
414 def quicksort(array):
415 size = array.getsize()
416 array.reset("Quicksort")
417 try:
418 stack = [(0, size)]
419 while stack:
420 first, last = stack[-1]
421 del stack[-1]
422 array.show_partition(first, last)
423 if last-first < 5:
424 array.message("Insertion sort")
425 for i in range(first+1, last):
426 j = i-1
427 while j >= first:
428 if array.compare(j, j+1) <= 0:
429 break
430 array.swap(j, j+1)
431 j = j-1
432 continue
433 array.message("Choosing pivot")
434 j, i, k = first, (first+last) // 2, last-1
435 if array.compare(k, i) < 0:
436 array.swap(k, i)
437 if array.compare(k, j) < 0:
438 array.swap(k, j)
439 if array.compare(j, i) < 0:
440 array.swap(j, i)
441 pivot = j
442 array.show_pivot(pivot)
443 array.message("Pivot at left of partition")
444 array.wait(1000)
445 left = first
446 right = last
447 while True:
448 array.message("Sweep right pointer")
449 right = right-1
450 array.show_right(right)
451 while right > first and array.compare(right, pivot) >= 0:
452 right = right-1
453 array.show_right(right)
454 array.message("Sweep left pointer")
455 left = left+1
456 array.show_left(left)
457 while left < last and array.compare(left, pivot) <= 0:
458 left = left+1
459 array.show_left(left)
460 if left > right:
461 array.message("End of partition")
462 break
463 array.message("Swap items")
464 array.swap(left, right)
465 array.message("Swap pivot back")
466 array.swap(pivot, right)
467 n1 = right-first
468 n2 = last-left
469 if n1 > 1: stack.append((first, right))
470 if n2 > 1: stack.append((left, last))
471 array.message("Sorted")
472 finally:
473 array.hide_partition()
474
475 def demosort(array):
476 while True:
477 for alg in [quicksort, insertionsort, selectionsort, bubblesort]:
478 randomize(array)
479 alg(array)
480
481
482 # Sort demo class -- usable as a Grail applet
483
484 class ESC[4;38;5;81mSortDemo:
485
486 def __init__(self, master, size=15):
487 self.master = master
488 self.size = size
489 self.busy = 0
490 self.array = Array(self.master)
491
492 self.botframe = Frame(master)
493 self.botframe.pack(side=BOTTOM)
494 self.botleftframe = Frame(self.botframe)
495 self.botleftframe.pack(side=LEFT, fill=Y)
496 self.botrightframe = Frame(self.botframe)
497 self.botrightframe.pack(side=RIGHT, fill=Y)
498
499 self.b_qsort = Button(self.botleftframe,
500 text="Quicksort", command=self.c_qsort)
501 self.b_qsort.pack(fill=X)
502 self.b_isort = Button(self.botleftframe,
503 text="Insertion sort", command=self.c_isort)
504 self.b_isort.pack(fill=X)
505 self.b_ssort = Button(self.botleftframe,
506 text="Selection sort", command=self.c_ssort)
507 self.b_ssort.pack(fill=X)
508 self.b_bsort = Button(self.botleftframe,
509 text="Bubble sort", command=self.c_bsort)
510 self.b_bsort.pack(fill=X)
511
512 # Terrible hack to overcome limitation of OptionMenu...
513 class ESC[4;38;5;81mMyIntVar(ESC[4;38;5;149mIntVar):
514 def __init__(self, master, demo):
515 self.demo = demo
516 IntVar.__init__(self, master)
517 def set(self, value):
518 IntVar.set(self, value)
519 if str(value) != '0':
520 self.demo.resize(value)
521
522 self.v_size = MyIntVar(self.master, self)
523 self.v_size.set(size)
524 sizes = [1, 2, 3, 4] + list(range(5, 55, 5))
525 if self.size not in sizes:
526 sizes.append(self.size)
527 sizes.sort()
528 self.m_size = OptionMenu(self.botleftframe, self.v_size, *sizes)
529 self.m_size.pack(fill=X)
530
531 self.v_speed = StringVar(self.master)
532 self.v_speed.set("normal")
533 self.m_speed = OptionMenu(self.botleftframe, self.v_speed,
534 "single-step", "normal", "fast", "fastest")
535 self.m_speed.pack(fill=X)
536
537 self.b_step = Button(self.botleftframe,
538 text="Step", command=self.c_step)
539 self.b_step.pack(fill=X)
540
541 self.b_randomize = Button(self.botrightframe,
542 text="Randomize", command=self.c_randomize)
543 self.b_randomize.pack(fill=X)
544 self.b_uniform = Button(self.botrightframe,
545 text="Uniform", command=self.c_uniform)
546 self.b_uniform.pack(fill=X)
547 self.b_distinct = Button(self.botrightframe,
548 text="Distinct", command=self.c_distinct)
549 self.b_distinct.pack(fill=X)
550 self.b_demo = Button(self.botrightframe,
551 text="Demo", command=self.c_demo)
552 self.b_demo.pack(fill=X)
553 self.b_cancel = Button(self.botrightframe,
554 text="Cancel", command=self.c_cancel)
555 self.b_cancel.pack(fill=X)
556 self.b_cancel.config(state=DISABLED)
557 self.b_quit = Button(self.botrightframe,
558 text="Quit", command=self.c_quit)
559 self.b_quit.pack(fill=X)
560
561 def resize(self, newsize):
562 if self.busy:
563 self.master.bell()
564 return
565 self.size = newsize
566 self.array.setdata(range(1, self.size+1))
567
568 def c_qsort(self):
569 self.run(quicksort)
570
571 def c_isort(self):
572 self.run(insertionsort)
573
574 def c_ssort(self):
575 self.run(selectionsort)
576
577 def c_bsort(self):
578 self.run(bubblesort)
579
580 def c_demo(self):
581 self.run(demosort)
582
583 def c_randomize(self):
584 self.run(randomize)
585
586 def c_uniform(self):
587 self.run(uniform)
588
589 def c_distinct(self):
590 self.run(distinct)
591
592 def run(self, func):
593 if self.busy:
594 self.master.bell()
595 return
596 self.busy = 1
597 self.array.setspeed(self.v_speed.get())
598 self.b_cancel.config(state=NORMAL)
599 try:
600 func(self.array)
601 except Array.Cancelled:
602 pass
603 self.b_cancel.config(state=DISABLED)
604 self.busy = 0
605
606 def c_cancel(self):
607 if not self.busy:
608 self.master.bell()
609 return
610 self.array.cancel()
611
612 def c_step(self):
613 if not self.busy:
614 self.master.bell()
615 return
616 self.v_speed.set("single-step")
617 self.array.setspeed("single-step")
618 self.array.step()
619
620 def c_quit(self):
621 if self.busy:
622 self.array.cancel()
623 self.master.after_idle(self.master.quit)
624
625
626 # Main program -- for stand-alone operation outside Grail
627
628 def main():
629 root = Tk()
630 demo = SortDemo(root)
631 root.protocol('WM_DELETE_WINDOW', demo.c_quit)
632 root.mainloop()
633
634 if __name__ == '__main__':
635 main()