1 #!/usr/bin/env python3
2 """
3
4 sorting_animation.py
5
6 A minimal sorting algorithm animation:
7 Sorts a shelf of 10 blocks using insertion
8 sort, selection sort and quicksort.
9
10 Shelfs are implemented using builtin lists.
11
12 Blocks are turtles with shape "square", but
13 stretched to rectangles by shapesize()
14 ---------------------------------------
15 To exit press space button
16 ---------------------------------------
17 """
18 from turtle import *
19 import random
20
21
22 class ESC[4;38;5;81mBlock(ESC[4;38;5;149mTurtle):
23
24 def __init__(self, size):
25 self.size = size
26 Turtle.__init__(self, shape="square", visible=False)
27 self.pu()
28 self.shapesize(size * 1.5, 1.5, 2) # square-->rectangle
29 self.fillcolor("black")
30 self.st()
31
32 def glow(self):
33 self.fillcolor("red")
34
35 def unglow(self):
36 self.fillcolor("black")
37
38 def __repr__(self):
39 return "Block size: {0}".format(self.size)
40
41
42 class ESC[4;38;5;81mShelf(ESC[4;38;5;149mlist):
43
44 def __init__(self, y):
45 "create a shelf. y is y-position of first block"
46 self.y = y
47 self.x = -150
48
49 def push(self, d):
50 width, _, _ = d.shapesize()
51 # align blocks by the bottom edge
52 y_offset = width / 2 * 20
53 d.sety(self.y + y_offset)
54 d.setx(self.x + 34 * len(self))
55 self.append(d)
56
57 def _close_gap_from_i(self, i):
58 for b in self[i:]:
59 xpos, _ = b.pos()
60 b.setx(xpos - 34)
61
62 def _open_gap_from_i(self, i):
63 for b in self[i:]:
64 xpos, _ = b.pos()
65 b.setx(xpos + 34)
66
67 def pop(self, key):
68 b = list.pop(self, key)
69 b.glow()
70 b.sety(200)
71 self._close_gap_from_i(key)
72 return b
73
74 def insert(self, key, b):
75 self._open_gap_from_i(key)
76 list.insert(self, key, b)
77 b.setx(self.x + 34 * key)
78 width, _, _ = b.shapesize()
79 # align blocks by the bottom edge
80 y_offset = width / 2 * 20
81 b.sety(self.y + y_offset)
82 b.unglow()
83
84 def isort(shelf):
85 length = len(shelf)
86 for i in range(1, length):
87 hole = i
88 while hole > 0 and shelf[i].size < shelf[hole - 1].size:
89 hole = hole - 1
90 shelf.insert(hole, shelf.pop(i))
91 return
92
93 def ssort(shelf):
94 length = len(shelf)
95 for j in range(0, length - 1):
96 imin = j
97 for i in range(j + 1, length):
98 if shelf[i].size < shelf[imin].size:
99 imin = i
100 if imin != j:
101 shelf.insert(j, shelf.pop(imin))
102
103 def partition(shelf, left, right, pivot_index):
104 pivot = shelf[pivot_index]
105 shelf.insert(right, shelf.pop(pivot_index))
106 store_index = left
107 for i in range(left, right): # range is non-inclusive of ending value
108 if shelf[i].size < pivot.size:
109 shelf.insert(store_index, shelf.pop(i))
110 store_index = store_index + 1
111 shelf.insert(store_index, shelf.pop(right)) # move pivot to correct position
112 return store_index
113
114 def qsort(shelf, left, right):
115 if left < right:
116 pivot_index = left
117 pivot_new_index = partition(shelf, left, right, pivot_index)
118 qsort(shelf, left, pivot_new_index - 1)
119 qsort(shelf, pivot_new_index + 1, right)
120
121 def randomize():
122 disable_keys()
123 clear()
124 target = list(range(10))
125 random.shuffle(target)
126 for i, t in enumerate(target):
127 for j in range(i, len(s)):
128 if s[j].size == t + 1:
129 s.insert(i, s.pop(j))
130 show_text(instructions1)
131 show_text(instructions2, line=1)
132 enable_keys()
133
134 def show_text(text, line=0):
135 line = 20 * line
136 goto(0,-250 - line)
137 write(text, align="center", font=("Courier", 16, "bold"))
138
139 def start_ssort():
140 disable_keys()
141 clear()
142 show_text("Selection Sort")
143 ssort(s)
144 clear()
145 show_text(instructions1)
146 show_text(instructions2, line=1)
147 enable_keys()
148
149 def start_isort():
150 disable_keys()
151 clear()
152 show_text("Insertion Sort")
153 isort(s)
154 clear()
155 show_text(instructions1)
156 show_text(instructions2, line=1)
157 enable_keys()
158
159 def start_qsort():
160 disable_keys()
161 clear()
162 show_text("Quicksort")
163 qsort(s, 0, len(s) - 1)
164 clear()
165 show_text(instructions1)
166 show_text(instructions2, line=1)
167 enable_keys()
168
169 def init_shelf():
170 global s
171 s = Shelf(-200)
172 vals = (4, 2, 8, 9, 1, 5, 10, 3, 7, 6)
173 for i in vals:
174 s.push(Block(i))
175
176 def disable_keys():
177 onkey(None, "s")
178 onkey(None, "i")
179 onkey(None, "q")
180 onkey(None, "r")
181
182 def enable_keys():
183 onkey(start_isort, "i")
184 onkey(start_ssort, "s")
185 onkey(start_qsort, "q")
186 onkey(randomize, "r")
187 onkey(bye, "space")
188
189 def main():
190 getscreen().clearscreen()
191 ht(); penup()
192 init_shelf()
193 show_text(instructions1)
194 show_text(instructions2, line=1)
195 enable_keys()
196 listen()
197 return "EVENTLOOP"
198
199 instructions1 = "press i for insertion sort, s for selection sort, q for quicksort"
200 instructions2 = "spacebar to quit, r to randomize"
201
202 if __name__=="__main__":
203 msg = main()
204 mainloop()