1#!/usr/bin/env python3
2
3"""
4Sorting algorithms visualizer using Tkinter.
5
6This module is comprised of three ``components'':
7
8- an array visualizer with methods that implement basic sorting
9operations (compare, swap) as well as methods for ``annotating'' the
10sorting algorithm (e.g. to show the pivot element);
11
12- a number of sorting algorithms (currently quicksort, insertion sort,
13selection sort and bubble sort, as well as a randomization function),
14all using the array visualizer for its basic operations and with calls
15to its annotation methods;
16
17- and a ``driver'' class which can be used as a Grail applet or as a
18stand-alone application.
19"""
20
21from tkinter import *
22import random
23
24XGRID = 10
25YGRID = 10
26WIDTH = 6
27
28
29class 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
194class 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
337def 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
347def 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
362def uniform(array):
363    size = array.getsize()
364    array.setdata([(size+1)//2] * size)
365    array.reset("Uniform data, size %d" % size)
366
367def distinct(array):
368    size = array.getsize()
369    array.setdata(range(1, size+1))
370    array.reset("Distinct data, size %d" % size)
371
372def 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
380def 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
392def 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
405def 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
414def 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
475def 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
484class 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
628def main():
629    root = Tk()
630    demo = SortDemo(root)
631    root.protocol('WM_DELETE_WINDOW', demo.c_quit)
632    root.mainloop()
633
634if __name__ == '__main__':
635    main()
636