Merge Sort algorithm is fast but it requires additional array and additional copying. Quick Sort is even faster than Merge Sort. Implement Quick Sort algorithm and animate it!
Here is the source code:
import turtle
import random
import time
screen = turtle.Screen()
screen.setup(1000,1000)
screen.tracer(0,0)
screen.title('Quick Sort Animation - PythonTurtle.Academy')
turtle.speed(0)
turtle.hideturtle()
def draw_bar(x,y,w,h):
turtle.up()
turtle.goto(x,y)
turtle.seth(0)
turtle.down()
turtle.begin_fill()
turtle.fd(w)
turtle.left(90)
turtle.fd(h)
turtle.left(90)
turtle.fd(w)
turtle.left(90)
turtle.fd(h)
turtle.left(90)
turtle.end_fill()
def draw_bars(v,n,currenti=-1,currentj=-1):
turtle.clear()
x = -400
w = 800/n
for i in range(n):
if i == currenti: turtle.fillcolor('red')
elif i == currentj: turtle.fillcolor('blue')
else: turtle.fillcolor('gray')
draw_bar(x,-400,w,v[i])
x += w
screen.update()
def partition(v,x,y):
p = random.randint(x,y)
v[p], v[y] = v[y], v[p]
pivot = v[y]
i, j = x, y-1
while i <= j:
while v[i] <= pivot and i <= j:
draw_bars(v,n,i,j)
i += 1
while v[j] > pivot and j >= i:
draw_bars(v,n,i,j)
j -= 1
if i < j:
draw_bars(v,n,i,j)
v[i], v[j] = v[j], v[i]
v[i], v[y] = v[y], v[i]
draw_bars(v,n,i,y)
return i
def quick_sort(v,x,y):
if x >= y:
return
m = partition(v,x,y)
quick_sort(v,x,m-1)
quick_sort(v,m+1,y)
n = 50
v = [0] * n
for i in range(n):
v[i] = random.randint(1,800)
t1 = time.time()
quick_sort(v,0,n-1)
turtle.clear()
draw_bars(v,n,-1)
turtle.update()
t2 = time.time()
print('elapsed time=', t2-t1)
In a previous Hypotrochoid project, you drew curves with two circles with one rolling inside the other. Expand the project by adding one more layer of circles. The following is some of the curves generated by three circle Hypotrochoid:
Thanks to Torry for contributing idea to this project.
Generate a random polygon with many sides and randomly drop point on the screen. If the point falls inside the polygon color it in red, otherwise color it in blue.
Continuing from previous Accelerating and Rotating Spaceship project, make the spaceship fire the bullets. Each bullet have limited range and there should be some time gap between the firings so that spaceship won’t destroy asteroids too easily in the future game. You may need to use list structure in Python to store the bullets.
This step should be straightforward. We just need n horizontal and n vertical lines centered in the screen. The following is the code snippet that draws the grid.
screen=turtle.Screen()
turtle.setup(1000,1000)
turtle.title("Conway's Game of Life - PythonTurtle.Academy")
turtle.hideturtle()
turtle.speed(0)
turtle.tracer(0,0)
n = 50 # nxn grid
def draw_line(x1,y1,x2,y2): # this function draw a line between x1,y1 and x2,y2
turtle.up()
turtle.goto(x1,y1)
turtle.down()
turtle.goto(x2,y2)
def draw_grid(): # this function draws nxn grid
turtle.pencolor('gray')
turtle.pensize(3)
x = -400
for i in range(n+1):
draw_line(x,-400,x,400)
x += 800/n
y = -400
for i in range(n+1):
draw_line(-400,y,400,y)
y += 800/n
draw_grid()
screen.update()
It should a grid like the following picture:
n x n grid
Step 2: Creating Life
We need data structure to store the lives in the n x n cells. The natural data structure for this purpose is a list of lists. We are going to use value 1 to represent ‘life’ and 0 to represent ‘no life’. The lives in cells will be randomly generated with 1/7 probability of having life. The following is the code snippet that creates and initializes lives:
life = list() # create an empty list
def init_lives():
for i in range(n):
liferow = [] # a row of lives
for j in range(n):
if random.randint(0,7) == 0: # 1/7 probability of life
liferow.append(1) # 1 means life
else:
liferow.append(0) # 0 means no life
life.append(liferow) # add a row to the life list -> life is a list of list
Step 3: Displaying Life in Cells
The next task is to draw live cells in the grid. We will create and use a new turtle called lifeturtle to draw the live cells. Because cells can become alive or dead, we need to erase them and redraw in each cycle. However, there is no need to erase the grid. By just clearing the lifeturtle, there is no need to redraw the grid. The following is complete code for the first 3 steps.
import turtle
import random
screen=turtle.Screen()
turtle.setup(1000,1000)
turtle.title("Conway's Game of Life - PythonTurtle.Academy")
turtle.hideturtle()
turtle.speed(0)
turtle.tracer(0,0)
lifeturtle = turtle.Turtle() # turtle for drawing life
lifeturtle.up()
lifeturtle.hideturtle()
lifeturtle.speed(0)
lifeturtle.color('black')
n = 50 # nxn grid
def draw_line(x1,y1,x2,y2): # this function draw a line between x1,y1 and x2,y2
turtle.up()
turtle.goto(x1,y1)
turtle.down()
turtle.goto(x2,y2)
def draw_grid(): # this function draws nxn grid
turtle.pencolor('gray')
turtle.pensize(3)
x = -400
for i in range(n+1):
draw_line(x,-400,x,400)
x += 800/n
y = -400
for i in range(n+1):
draw_line(-400,y,400,y)
y += 800/n
life = list() # create an empty list
def init_lives():
for i in range(n):
liferow = [] # a row of lives
for j in range(n):
if random.randint(0,7) == 0: # 1/7 probability of life
liferow.append(1) # 1 means life
else:
liferow.append(0) # 0 means no life
life.append(liferow) # add a row to the life list -> life is a list of list
def draw_square(x,y,size): # draws a filled square
lifeturtle.up()
lifeturtle.goto(x,y)
lifeturtle.down()
lifeturtle.seth(0)
lifeturtle.begin_fill()
for i in range(4):
lifeturtle.fd(size)
lifeturtle.left(90)
lifeturtle.end_fill()
def draw_life(x,y): # draws life in (x,y)
lx = 800/n*x - 400 # converts x,y to screen coordinate
ly = 800/n*y - 400
draw_square(lx+1,ly+1,800/n-2)
def draw_all_life(): # draws all life
global life
for i in range(n):
for j in range(n):
if life[i][j] == 1: draw_life(i,j) # draw live cells
draw_grid()
init_lives()
draw_all_life()
screen.update()
It should draw a shape like the following image:
Step 4: Updating Life Forever
The next step is to update the life based on the Conway’s Rule:
If a cell with fewer than two or more than three live neighbors dies because of underpopulation or overpopulation.
If a live cell has two or three live neighbors, the cell survives to the next generation.
If a dead cell has exactly three live neighbors, it becomes alive.
We will create a function update_life() that will update the cells based on these rules. Then we will call this function again with the Turtle’s timer event. The following is the complete code for animating the Conway’s Game of Life:
import turtle
import random
import copy
screen=turtle.Screen()
turtle.setup(1000,1000)
turtle.title("Conway's Game of Life - PythonTurtle.Academy")
turtle.hideturtle()
turtle.speed(0)
turtle.tracer(0,0)
lifeturtle = turtle.Turtle() # turtle for drawing life
lifeturtle.up()
lifeturtle.hideturtle()
lifeturtle.speed(0)
lifeturtle.color('black')
n = 50 # nxn grid
def draw_line(x1,y1,x2,y2): # this function draw a line between x1,y1 and x2,y2
turtle.up()
turtle.goto(x1,y1)
turtle.down()
turtle.goto(x2,y2)
def draw_grid(): # this function draws nxn grid
turtle.pencolor('gray')
turtle.pensize(3)
x = -400
for i in range(n+1):
draw_line(x,-400,x,400)
x += 800/n
y = -400
for i in range(n+1):
draw_line(-400,y,400,y)
y += 800/n
life = list() # create an empty list
def init_lives():
for i in range(n):
liferow = [] # a row of lives
for j in range(n):
if random.randint(0,7) == 0: # 1/7 probability of life
liferow.append(1) # 1 means life
else:
liferow.append(0) # 0 means no life
life.append(liferow) # add a row to the life list -> life is a list of list
def draw_square(x,y,size): # draws a filled square
lifeturtle.up()
lifeturtle.goto(x,y)
lifeturtle.down()
lifeturtle.seth(0)
lifeturtle.begin_fill()
for i in range(4):
lifeturtle.fd(size)
lifeturtle.left(90)
lifeturtle.end_fill()
def draw_life(x,y): # draws life in (x,y)
lx = 800/n*x - 400 # converts x,y to screen coordinate
ly = 800/n*y - 400
draw_square(lx+1,ly+1,800/n-2)
def draw_all_life(): # draws all life
global life
for i in range(n):
for j in range(n):
if life[i][j] == 1: draw_life(i,j) # draw live cells
def num_neighbors(x,y): # computes the number of life neighbours for cell[x,y]
sum = 0
for i in range(max(x-1,0),min(x+1,n-1)+1):
for j in range(max(y-1,0),min(y+1,n-1)+1):
sum += life[i][j]
return sum - life[x][y]
def update_life(): # update life for each cycle
global life
newlife = copy.deepcopy(life) # make a copy of life
for i in range(n):
for j in range(n):
k = num_neighbors(i,j)
if k < 2 or k > 3:
newlife[i][j] = 0
elif k == 3:
newlife[i][j] = 1
life = copy.deepcopy(newlife) # copy back to life
lifeturtle.clear() # clears life in previous cycle
draw_all_life()
screen.update()
screen.ontimer(update_life,200) # update life every 0.2 second
draw_grid()
init_lives()
update_life()
Let’s take a look at the the following unfilled cloud picture. As you can see, we drew the cloud just by drawing many arcs of different sizes and extent.
Unfilled Cloud
The problem is how we can draw this arcs to form the shape of a cloud (You can try randomly draw these arcs to see what shape it forms). The solution is to use an oval shape to control the end points of these arcs. As you can see in the following picture, the arcs starts and ends on the points of an oval shape.
Arcs Starts and Ends on the Oval Shape
Here is the general idea of the algorithm for drawing the cloud shape: 1. Create an oval shape and put the coordinates of points on the oval into a list. 2. Starting from a point in the list, randomly skip certain number of points and stop on another point. 3. Use two points from step 2, decide the extent of arc randomly and draw the arc. 4. Repeat 2,3 until all the points on the oval is covered.
Now let’s get into the details:
Creating the Oval
We can use two halves of ellipses to draw the oval shape. Because clouds have flatter bottom than the top, we should make top ellipse is taller than the bottom one. Both of them should have the same width. The easiest way to create this shape is to use parametric equations for ellipse. The following is the code snippet:
n = 500 # number of points on each ellipse
# X,Y is the center of ellipse, a is radius on x-axis, b is radius on y-axis
# ts is the starting angle of the ellipse, te is the ending angle of the ellipse
# P is the list of coordinates of the points on the ellipse
def ellipse(X,Y,a,b,ts,te,P):
t = ts
turtle.up()
for i in range(n):
x = a*math.cos(t)
y = b*math.sin(t)
P.append((x+X,y+Y))
turtle.goto(x+X,y+Y)
turtle.down()
t += (te-ts)/(n-1)
P = [] # starting from empty list
ellipse(0,0,300,200,0,math.pi,P) # taller top half
ellipse(0,0,300,50,math.pi,math.pi*2,P) # shorter bottom half
Drawing an Random Arc
The next problem we need to solve is: how can we draw an arc given two points and extent? We need to figure out the radius and the initial heading for drawing the circle. This requires some geometry work details of which will be skipped for this tutorial. The following code snippet for this part:
# computes Euclidean distance between p1 and p2
def dist(p1,p2):
return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**0.5
# draws an arc from p1 to p2 with extent value ext
def draw_arc(p1,p2,ext):
turtle.up()
turtle.goto(p1)
turtle.seth(turtle.towards(p2))
a = turtle.heading()
b = 360-ext
c = (180-b)/2
d = a-c
e = d-90
r = dist(p1,p2)/2/math.sin(math.radians(b/2)) # r is the radius of the arc
turtle.seth(e) # e is initial heading of the circle
turtle.down()
turtle.circle(r,ext,100)
return (turtle.xcor(),turtle.ycor()) # returns the landing position of the circle
# this position should be extremely close to p2 but may not be exactly the same
# return this for continuous drawing to the next point
draw_arc((0,0), (-100,200), 150)
Drawing the Cloud
With previous two sections done, we are ready to draw the cloud. We randomly skip a number of points to get to the next point, randomly generate an extent, and draw the arc between these two points. This is to be repeated until all points are covered. There are a few details to address. The top part of cloud is more ragged than the bottom part. Therefore, we should give wider range for the extent and steps for random number generator. The following is the complete code for drawing clouds:
import turtle
import math
import random
screen = turtle.Screen()
screen.setup(1000,1000)
screen.title("Random Cloud - PythonTurtle.Academy")
turtle.speed(0)
turtle.hideturtle()
turtle.up()
turtle.bgcolor('dodger blue')
turtle.pencolor('white')
turtle.pensize(2)
n = 500 # number of points on each ellipse
# X,Y is the center of ellipse, a is radius on x-axis, b is radius on y-axis
# ts is the starting angle of the ellipse, te is the ending angle of the ellipse
# P is the list of coordinates of the points on the ellipse
def ellipse(X,Y,a,b,ts,te,P):
t = ts
for i in range(n):
x = a*math.cos(t)
y = b*math.sin(t)
P.append((x+X,y+Y))
t += (te-ts)/(n-1)
# computes Euclidean distance between p1 and p2
def dist(p1,p2):
return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**0.5
# draws an arc from p1 to p2 with extent value ext
def draw_arc(p1,p2,ext):
turtle.up()
turtle.goto(p1)
turtle.seth(turtle.towards(p2))
a = turtle.heading()
b = 360-ext
c = (180-b)/2
d = a-c
e = d-90
r = dist(p1,p2)/2/math.sin(math.radians(b/2)) # r is the radius of the arc
turtle.seth(e) # e is initial heading of the circle
turtle.down()
turtle.circle(r,ext,100)
return (turtle.xcor(),turtle.ycor()) # returns the landing position of the circle
# this position should be extremely close to p2 but may not be exactly the same
# return this for continuous drawing to the next point
def cloud(P):
step = n//10 # draw about 10 arcs on top and bottom part of cloud
a = 0 # a is index of first point
b = a + random.randint(step//2,step*2) # b is index of second point
p1 = P[a] # p1 is the position of the first point
p2 = P[b] # p2 is the position of the second point
turtle.fillcolor('white')
turtle.begin_fill()
p3 = draw_arc(p1,p2,random.uniform(70,180)) # draws the arc with random extention
while b < len(P)-1:
p1 = p3 # start from the end of the last arc
if b < len(P)/2: # first half is top, more ragged
ext = random.uniform(70,180)
b += random.randint(step//2,step*2)
else: # second half is bottom, more smooth
ext = random.uniform(30,70)
b += random.randint(step,step*2)
b = min(b,len(P)-1) # make sure to not skip past the last point
p2 = P[b] # second point
p3 = draw_arc(p1,p2,ext) # draws an arc and return the end position
turtle.end_fill()
P = [] # starting from empty list
ellipse(0,0,300,200,0,math.pi,P) # taller top half
ellipse(0,0,300,50,math.pi,math.pi*2,P) # shorter bottom half
cloud(P)
