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 Array: 30 31 class Cancelled(BaseException): 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 ArrayItem: 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 1: 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 1: 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 SortDemo: 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 MyIntVar(IntVar): 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() 636
