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