Debian Codegraph @

Lib/turtledemo/sorting_animate.py

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