sorting_animate.py (5052B)
- #!/usr/bin/env python3
- """
- sorting_animation.py
- A minimal sorting algorithm animation:
- Sorts a shelf of 10 blocks using insertion
- sort, selection sort and quicksort.
- Shelfs are implemented using builtin lists.
- Blocks are turtles with shape "square", but
- stretched to rectangles by shapesize()
- ---------------------------------------
- To exit press space button
- ---------------------------------------
- """
- from turtle import *
- import random
- class Block(Turtle):
- def __init__(self, size):
- self.size = size
- Turtle.__init__(self, shape="square", visible=False)
- self.pu()
- self.shapesize(size * 1.5, 1.5, 2) # square-->rectangle
- self.fillcolor("black")
- self.st()
- def glow(self):
- self.fillcolor("red")
- def unglow(self):
- self.fillcolor("black")
- def __repr__(self):
- return "Block size: {0}".format(self.size)
- class Shelf(list):
- def __init__(self, y):
- "create a shelf. y is y-position of first block"
- self.y = y
- self.x = -150
- def push(self, d):
- width, _, _ = d.shapesize()
- # align blocks by the bottom edge
- y_offset = width / 2 * 20
- d.sety(self.y + y_offset)
- d.setx(self.x + 34 * len(self))
- self.append(d)
- def _close_gap_from_i(self, i):
- for b in self[i:]:
- xpos, _ = b.pos()
- b.setx(xpos - 34)
- def _open_gap_from_i(self, i):
- for b in self[i:]:
- xpos, _ = b.pos()
- b.setx(xpos + 34)
- def pop(self, key):
- b = list.pop(self, key)
- b.glow()
- b.sety(200)
- self._close_gap_from_i(key)
- return b
- def insert(self, key, b):
- self._open_gap_from_i(key)
- list.insert(self, key, b)
- b.setx(self.x + 34 * key)
- width, _, _ = b.shapesize()
- # align blocks by the bottom edge
- y_offset = width / 2 * 20
- b.sety(self.y + y_offset)
- b.unglow()
- def isort(shelf):
- length = len(shelf)
- for i in range(1, length):
- hole = i
- while hole > 0 and shelf[i].size < shelf[hole - 1].size:
- hole = hole - 1
- shelf.insert(hole, shelf.pop(i))
- return
- def ssort(shelf):
- length = len(shelf)
- for j in range(0, length - 1):
- imin = j
- for i in range(j + 1, length):
- if shelf[i].size < shelf[imin].size:
- imin = i
- if imin != j:
- shelf.insert(j, shelf.pop(imin))
- def partition(shelf, left, right, pivot_index):
- pivot = shelf[pivot_index]
- shelf.insert(right, shelf.pop(pivot_index))
- store_index = left
- for i in range(left, right): # range is non-inclusive of ending value
- if shelf[i].size < pivot.size:
- shelf.insert(store_index, shelf.pop(i))
- store_index = store_index + 1
- shelf.insert(store_index, shelf.pop(right)) # move pivot to correct position
- return store_index
- def qsort(shelf, left, right):
- if left < right:
- pivot_index = left
- pivot_new_index = partition(shelf, left, right, pivot_index)
- qsort(shelf, left, pivot_new_index - 1)
- qsort(shelf, pivot_new_index + 1, right)
- def randomize():
- disable_keys()
- clear()
- target = list(range(10))
- random.shuffle(target)
- for i, t in enumerate(target):
- for j in range(i, len(s)):
- if s[j].size == t + 1:
- s.insert(i, s.pop(j))
- show_text(instructions1)
- show_text(instructions2, line=1)
- enable_keys()
- def show_text(text, line=0):
- line = 20 * line
- goto(0,-250 - line)
- write(text, align="center", font=("Courier", 16, "bold"))
- def start_ssort():
- disable_keys()
- clear()
- show_text("Selection Sort")
- ssort(s)
- clear()
- show_text(instructions1)
- show_text(instructions2, line=1)
- enable_keys()
- def start_isort():
- disable_keys()
- clear()
- show_text("Insertion Sort")
- isort(s)
- clear()
- show_text(instructions1)
- show_text(instructions2, line=1)
- enable_keys()
- def start_qsort():
- disable_keys()
- clear()
- show_text("Quicksort")
- qsort(s, 0, len(s) - 1)
- clear()
- show_text(instructions1)
- show_text(instructions2, line=1)
- enable_keys()
- def init_shelf():
- global s
- s = Shelf(-200)
- vals = (4, 2, 8, 9, 1, 5, 10, 3, 7, 6)
- for i in vals:
- s.push(Block(i))
- def disable_keys():
- onkey(None, "s")
- onkey(None, "i")
- onkey(None, "q")
- onkey(None, "r")
- def enable_keys():
- onkey(start_isort, "i")
- onkey(start_ssort, "s")
- onkey(start_qsort, "q")
- onkey(randomize, "r")
- onkey(bye, "space")
- def main():
- getscreen().clearscreen()
- ht(); penup()
- init_shelf()
- show_text(instructions1)
- show_text(instructions2, line=1)
- enable_keys()
- listen()
- return "EVENTLOOP"
- instructions1 = "press i for insertion sort, s for selection sort, q for quicksort"
- instructions2 = "spacebar to quit, r to randomize"
- if __name__=="__main__":
- msg = main()
- mainloop()