Home | History | Annotate | Download | only in turtledemo 
      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 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 
     42 class 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 
     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()
    205