logo

oasis-root

Compiled tree of Oasis Linux based on own branch at <https://hacktivis.me/git/oasis/> git clone https://anongit.hacktivis.me/git/oasis-root.git

sorting_animate.py (5052B)


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