Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 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): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 51 | |
| 52 | def setdata(self, data): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 64 | |
| 65 | speed = "normal" |
| 66 | |
| 67 | def setspeed(self, speed): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 68 | self.speed = speed |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 69 | |
| 70 | def destroy(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 71 | self.frame.destroy() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 72 | |
| 73 | in_mainloop = 0 |
| 74 | stop_mainloop = 0 |
| 75 | |
| 76 | def cancel(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 77 | self.stop_mainloop = 1 |
| 78 | if self.in_mainloop: |
| 79 | self.master.quit() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 80 | |
| 81 | def step(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 82 | if self.in_mainloop: |
| 83 | self.master.quit() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 84 | |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 85 | Cancelled = "Array.Cancelled" # Exception |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 86 | |
| 87 | def wait(self, msecs): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 105 | |
| 106 | def getsize(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 107 | return self.size |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 108 | |
| 109 | def show_partition(self, first, last): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 117 | |
| 118 | def hide_partition(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 119 | for i in range(self.size): |
| 120 | item = self.items[i] |
| 121 | item.item.config(fill='red') |
| 122 | self.hide_left_right_pivot() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 123 | |
| 124 | def show_left(self, left): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 132 | |
| 133 | def show_right(self, right): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 140 | |
| 141 | def hide_left_right_pivot(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 142 | self.hide_left() |
| 143 | self.hide_right() |
| 144 | self.hide_pivot() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 145 | |
| 146 | def hide_left(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 147 | self.left.coords(((0, 0), (0, 0))) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 148 | |
| 149 | def hide_right(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 150 | self.right.coords(((0, 0), (0, 0))) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 151 | |
| 152 | def show_pivot(self, pivot): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 153 | x1, y1, x2, y2 = self.items[pivot].position() |
| 154 | self.pivot.coords(((0, y1-2), (9999, y1-2))) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 155 | |
| 156 | def hide_pivot(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 157 | self.pivot.coords(((0, 0), (0, 0))) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 158 | |
| 159 | def swap(self, i, j): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 166 | |
| 167 | def compare(self, i, j): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 168 | self.countcompare() |
| 169 | item = self.items[i] |
| 170 | other = self.items[j] |
| 171 | return item.compareto(other) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 172 | |
| 173 | def reset(self, msg): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 174 | self.ncompares = 0 |
| 175 | self.nswaps = 0 |
| 176 | self.message(msg) |
| 177 | self.updatereport() |
| 178 | self.hide_partition() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 179 | |
| 180 | def message(self, msg): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 181 | self.label.config(text=msg) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 182 | |
| 183 | def countswap(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 184 | self.nswaps = self.nswaps + 1 |
| 185 | self.updatereport() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 186 | |
| 187 | def countcompare(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 188 | self.ncompares = self.ncompares + 1 |
| 189 | self.updatereport() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 190 | |
| 191 | def updatereport(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 192 | text = "%d cmps, %d swaps" % (self.ncompares, self.nswaps) |
| 193 | self.report.config(text=text) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 194 | |
| 195 | |
| 196 | class ArrayItem: |
| 197 | |
| 198 | def __init__(self, array, index, value): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 208 | |
| 209 | def delete(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 210 | item = self.item |
| 211 | self.array = None |
| 212 | self.item = None |
| 213 | item.delete() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 214 | |
| 215 | def mouse_down(self, event): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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 | |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 222 | def mouse_move(self, event): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 223 | self.item.move(event.x - self.lastx, event.y - self.lasty) |
| 224 | self.lastx = event.x |
| 225 | self.lasty = event.y |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 226 | |
| 227 | def mouse_up(self, event): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 240 | |
| 241 | def setindex(self, index): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 254 | |
| 255 | def swapwith(self, other): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 300 | |
| 301 | def compareto(self, other): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 321 | |
| 322 | def position(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 328 | |
| 329 | def nearestindex(self, x): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 330 | return int(round(float(x)/XGRID)) - 1 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 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: |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 338 | nsteps = nsteps * 3 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 339 | elif nsteps <= 5: |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 340 | nsteps = nsteps * 2 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 341 | elif nsteps > 10: |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 342 | nsteps = 10 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 343 | return nsteps |
| 344 | |
| 345 | def interpolate(oldpts, newpts, n): |
| 346 | if len(oldpts) != len(newpts): |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 347 | raise ValueError("can't interpolate arrays of different length") |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 348 | pts = [0]*len(oldpts) |
| 349 | res = [tuple(oldpts)] |
| 350 | for i in range(1, n): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 351 | for k in range(len(pts)): |
| 352 | pts[k] = oldpts[k] + (newpts[k] - oldpts[k])*i/n |
| 353 | res.append(tuple(pts)) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 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): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 374 | j = random.randint(0, n-1) |
| 375 | array.swap(i, j) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 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): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 388 | array.message("Sorted") |
| 389 | |
| 390 | def selectionsort(array): |
| 391 | size = array.getsize() |
| 392 | array.reset("Selection sort") |
| 393 | try: |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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") |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 400 | finally: |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 401 | array.hide_partition() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 402 | |
| 403 | def bubblesort(array): |
| 404 | size = array.getsize() |
| 405 | array.reset("Bubble sort") |
| 406 | for i in range(size): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 407 | for j in range(1, size): |
| 408 | if array.compare(j-1, j) > 0: |
| 409 | array.swap(j-1, j) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 410 | array.message("Sorted") |
| 411 | |
| 412 | def quicksort(array): |
| 413 | size = array.getsize() |
| 414 | array.reset("Quicksort") |
| 415 | try: |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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") |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 470 | finally: |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 471 | array.hide_partition() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 472 | |
| 473 | def demosort(array): |
| 474 | while 1: |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 475 | for alg in [quicksort, insertionsort, selectionsort, bubblesort]: |
| 476 | randomize(array) |
| 477 | alg(array) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 478 | |
| 479 | |
| 480 | # Sort demo class -- usable as a Grail applet |
| 481 | |
| 482 | class SortDemo: |
| 483 | |
| 484 | def __init__(self, master, size=15): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 485 | self.master = master |
| 486 | self.size = size |
| 487 | self.busy = 0 |
| 488 | self.array = Array(self.master) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 489 | |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 496 | |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 509 | |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 519 | |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 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() |
Neal Norwitz | d910855 | 2006-03-17 08:00:19 +0000 | [diff] [blame] | 526 | self.m_size = OptionMenu(self.botleftframe, self.v_size, *sizes) |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 527 | self.m_size.pack(fill=X) |
| 528 | |
| 529 | self.v_speed = StringVar(self.master) |
| 530 | self.v_speed.set("normal") |
| 531 | self.m_speed = OptionMenu(self.botleftframe, self.v_speed, |
| 532 | "single-step", "normal", "fast", "fastest") |
| 533 | self.m_speed.pack(fill=X) |
| 534 | |
| 535 | self.b_step = Button(self.botleftframe, |
| 536 | text="Step", command=self.c_step) |
| 537 | self.b_step.pack(fill=X) |
| 538 | |
| 539 | self.b_randomize = Button(self.botrightframe, |
| 540 | text="Randomize", command=self.c_randomize) |
| 541 | self.b_randomize.pack(fill=X) |
| 542 | self.b_uniform = Button(self.botrightframe, |
| 543 | text="Uniform", command=self.c_uniform) |
| 544 | self.b_uniform.pack(fill=X) |
| 545 | self.b_distinct = Button(self.botrightframe, |
| 546 | text="Distinct", command=self.c_distinct) |
| 547 | self.b_distinct.pack(fill=X) |
| 548 | self.b_demo = Button(self.botrightframe, |
| 549 | text="Demo", command=self.c_demo) |
| 550 | self.b_demo.pack(fill=X) |
| 551 | self.b_cancel = Button(self.botrightframe, |
| 552 | text="Cancel", command=self.c_cancel) |
| 553 | self.b_cancel.pack(fill=X) |
| 554 | self.b_cancel.config(state=DISABLED) |
| 555 | self.b_quit = Button(self.botrightframe, |
| 556 | text="Quit", command=self.c_quit) |
| 557 | self.b_quit.pack(fill=X) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 558 | |
| 559 | def resize(self, newsize): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 560 | if self.busy: |
| 561 | self.master.bell() |
| 562 | return |
| 563 | self.size = newsize |
| 564 | self.array.setdata(range(1, self.size+1)) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 565 | |
| 566 | def c_qsort(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 567 | self.run(quicksort) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 568 | |
| 569 | def c_isort(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 570 | self.run(insertionsort) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 571 | |
| 572 | def c_ssort(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 573 | self.run(selectionsort) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 574 | |
| 575 | def c_bsort(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 576 | self.run(bubblesort) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 577 | |
| 578 | def c_demo(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 579 | self.run(demosort) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 580 | |
| 581 | def c_randomize(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 582 | self.run(randomize) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 583 | |
| 584 | def c_uniform(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 585 | self.run(uniform) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 586 | |
| 587 | def c_distinct(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 588 | self.run(distinct) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 589 | |
| 590 | def run(self, func): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 591 | if self.busy: |
| 592 | self.master.bell() |
| 593 | return |
| 594 | self.busy = 1 |
| 595 | self.array.setspeed(self.v_speed.get()) |
| 596 | self.b_cancel.config(state=NORMAL) |
| 597 | try: |
| 598 | func(self.array) |
| 599 | except Array.Cancelled: |
| 600 | pass |
| 601 | self.b_cancel.config(state=DISABLED) |
| 602 | self.busy = 0 |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 603 | |
| 604 | def c_cancel(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 605 | if not self.busy: |
| 606 | self.master.bell() |
| 607 | return |
| 608 | self.array.cancel() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 609 | |
| 610 | def c_step(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 611 | if not self.busy: |
| 612 | self.master.bell() |
| 613 | return |
| 614 | self.v_speed.set("single-step") |
| 615 | self.array.setspeed("single-step") |
| 616 | self.array.step() |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 617 | |
| 618 | def c_quit(self): |
Tim Peters | 182b5ac | 2004-07-18 06:16:08 +0000 | [diff] [blame] | 619 | if self.busy: |
| 620 | self.array.cancel() |
| 621 | self.master.after_idle(self.master.quit) |
Guido van Rossum | 9a8cb84 | 1997-04-03 00:04:51 +0000 | [diff] [blame] | 622 | |
| 623 | |
| 624 | # Main program -- for stand-alone operation outside Grail |
| 625 | |
| 626 | def main(): |
| 627 | root = Tk() |
| 628 | demo = SortDemo(root) |
| 629 | root.protocol('WM_DELETE_WINDOW', demo.c_quit) |
| 630 | root.mainloop() |
| 631 | |
| 632 | if __name__ == '__main__': |
| 633 | main() |