diff options
| -rw-r--r-- | Doc/library/turtle.rst | 3 | ||||
| -rw-r--r-- | Lib/turtledemo/sorting_animate.py | 204 | ||||
| -rw-r--r-- | Misc/NEWS | 3 |
3 files changed, 210 insertions, 0 deletions
diff --git a/Doc/library/turtle.rst b/Doc/library/turtle.rst index 157fe93..30dd6ef 100644 --- a/Doc/library/turtle.rst +++ b/Doc/library/turtle.rst @@ -2351,6 +2351,9 @@ The demo scripts are: | | pairwise in opposite | shapesize, tilt, | | | direction | get_shapepoly, update | +----------------+------------------------------+-----------------------+ +| sorting_animate| visual demonstration of | simple alignment, | +| | different sorting methods | randomization | ++----------------+------------------------------+-----------------------+ | tree | a (graphical) breadth | :func:`clone` | | | first tree (using generators)| | +----------------+------------------------------+-----------------------+ diff --git a/Lib/turtledemo/sorting_animate.py b/Lib/turtledemo/sorting_animate.py new file mode 100644 index 0000000..d25a0ab --- /dev/null +++ b/Lib/turtledemo/sorting_animate.py @@ -0,0 +1,204 @@ +#!/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() @@ -86,6 +86,9 @@ Library argument which, if set to True, will pass messages to handlers taking handler levels into account. +- Issue #19705: turtledemo now has a visual sorting algorithm demo. Original + patch from Jason Yeo. + Build ----- |