• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/env python3
2"""
3
4         sorting_animation.py
5
6A minimal sorting algorithm animation:
7Sorts a shelf of 10 blocks using insertion
8sort, selection sort and quicksort.
9
10Shelfs are implemented using builtin lists.
11
12Blocks are turtles with shape "square", but
13stretched to rectangles by shapesize()
14 ---------------------------------------
15       To exit press space button
16 ---------------------------------------
17"""
18from turtle import *
19import random
20
21
22class Block(Turtle):
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
42class Shelf(list):
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
84def 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
93def 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
103def 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
114def 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
121def 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
134def show_text(text, line=0):
135    line = 20 * line
136    goto(0,-250 - line)
137    write(text, align="center", font=("Courier", 16, "bold"))
138
139def 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
149def 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
159def 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
169def 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
176def disable_keys():
177    onkey(None, "s")
178    onkey(None, "i")
179    onkey(None, "q")
180    onkey(None, "r")
181
182def 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
189def 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
199instructions1 = "press i for insertion sort, s for selection sort, q for quicksort"
200instructions2 = "spacebar to quit, r to randomize"
201
202if __name__=="__main__":
203    msg = main()
204    mainloop()
205