Monthly Archives: September 2019

Triangle Snowflakes (with Source Code)

Posted on by

Draw the following shape of triangles with recursion.

import turtle

screen = turtle.Screen()
screen.setup(1000,1000)
screen.tracer(0,0)
screen.title('Recursive Triangles - PythonTurtle.Academy')
turtle.hideturtle()

def draw_triangle(x,y,s,angle):
    turtle.up()
    turtle.seth(angle)
    turtle.goto(x,y)
    turtle.fd(s/3**0.5)
    turtle.right(150)
    turtle.down()
    turtle.color('dodger blue')
    turtle.begin_fill()
    turtle.fd(s)
    turtle.right(120)
    turtle.fd(s)
    turtle.right(120)
    turtle.fd(s)
    turtle.end_fill()
    
def recursive_triangles(x,y,s,angle,n):
    if n==0: return
    turtle.goto(x,y)
    draw_triangle(x,y,s,angle)
    a = angle+60
    for _ in range(3):
        turtle.up()
        turtle.goto(x,y)
        turtle.seth(a)
        turtle.fd(1.3*s)
        x1,y1 = turtle.xcor(), turtle.ycor()
        recursive_triangles(x1,y1,s/2.1,a,n-1)
        a += 120

recursive_triangles(0,50,200,90,7)

screen.update()

Square Snowflake with Python Turtle (Source Code)

Posted on by

Draw the following square snowflake with recursion.

Source Code:

import turtle

screen = turtle.Screen()
screen.setup(1000,1000)
screen.tracer(0,0)
screen.title('Square Snowflake - PythonTurtle.Academy')
turtle.hideturtle()

def draw_square(x,y,s):
    turtle.up()
    turtle.goto(x-s/2,y-s/2)
    turtle.down()
    turtle.seth(0)
    turtle.fillcolor('sky blue')
    turtle.begin_fill()
    turtle.fd(s)
    turtle.left(90)
    turtle.fd(s)
    turtle.left(90)
    turtle.fd(s)
    turtle.left(90)
    turtle.fd(s)
    turtle.left(90)
    turtle.end_fill()
    
def draw_squares(x,y,s,n):
    if n == 0: return

    draw_square(x,y,s)
    draw_squares(x+s*1.5,y,s/2.5,n-1)
    draw_squares(x,y+s*1.5,s/2.5,n-1)
    draw_squares(x,y-s*1.5,s/2.5,n-1)
    draw_squares(x-s*1.5,y,s/2.5,n-1)

draw_squares(0,0,200,6)
screen.update()

Quick Sort Animation with Python and Turtle (with Source Code)

Posted on by

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)

Merge Sort Animation with Python and Turtle (with Source Code)

Posted on by

In previous sorting animations, we animated selection, insertion, and bubble sort. They are slow O(n^2) slow sorting algorithm. Merge Sort, a divide and conquer algorithm, is a much faster sorting algorithm with the worst case running time of O(n*logn). However, unlike previous sorting algorithms, it requires another array to be able to merge. Implement Merge Sorting and animate it!

Here is the source code:

import turtle
import random
import time

screen = turtle.Screen()
screen.setup(1000,1000)
screen.setworldcoordinates(-1000,-1000,1000,1000)
screen.tracer(0,0)
screen.title('Merge 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,w,n,currenti=-1,currentj=-1):
    turtle.clear()
    x = -400
    wd = 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,100,wd,v[i])
        x += wd
        
    x = -400
    for  i in range(n):
        turtle.fillcolor('gray')
        draw_bar(x,-900,wd,w[i])
        x += wd
    screen.update()

def merge(v,w,a,b,x,y):
    i,j, k = a,x,a
    while i<=b and j<=y:
        if v[i] < v[j]: w[k],i = v[i], i+1
        else: w[k], j = v[j], j+1
        draw_bars(v,w,n,i,j)
        k += 1
    while i<=b:
        w[k],i,k = v[i],i+1,k+1
        draw_bars(v,w,n,i,j)
    while j<=y:
        w[k],j,k = v[j],j+1,k+1
        draw_bars(v,w,n,i,j)
    for i in range(a,y+1):
        v[i] = w[i]
        draw_bars(v,w,n,i)
    
def merge_sort(v,w,x,y):
    if x >= y:
        return
    m = (x+y)//2
    merge_sort(v,w,x,m)
    merge_sort(v,w,m+1,y)
    merge(v,w,x,m,m+1,y)
    
n = 50
v = [0] * n
w = [0] * n
for i in range(n):
    v[i] = random.randint(1,800)

t1 = time.time()
merge_sort(v,w,0,n-1)
t2 = time.time()
print('elapsed time=', t2-t1)

What’s Next?

Quick Sort Animation