ยปCore Development>Code coverage>Lib/turtledemo/sorting_animate.py

Python code coverage for Lib/turtledemo/sorting_animate.py

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