Category Archives: list

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

Selection Sort Animation with Python and Turtle (Source Code Included)

Posted on by

Generate 50 random numbers and draw them as bars. Following the steps of selection sort algorithm and redraw the bar every single step to show how bubble sort works.

Compare against Bubble Sort and Insertion Sort. Which is the fastest? Which is the slowest?

Source Code:

import turtle
import random
import time

screen = turtle.Screen()
screen.setup(1000,1000)
screen.tracer(0,0)
screen.title('Selection 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,current):
    x = -400
    w = 800/n
    for  i in range(n):
        if i == current: turtle.fillcolor('red')
        else: turtle.fillcolor('gray')
        draw_bar(x,-400,w,v[i])
        x += w

def select_smallest(v,i,k):
    smallest = v[i]
    smallest_index = i
    for j in range(i+1,k):
        if v[j] < smallest:
            smallest = v[j]
            smallest_index = j
        turtle.clear()
        draw_bars(v,n,j)
        turtle.update()
    return smallest_index
        
def selection_sort(v,k):
    for i in range(k-1):
        j = select_smallest(v,i,k) # smallest index from ith to last
        v[i], v[j] = v[j], v[i] # swap with the smallest
        turtle.clear()
        draw_bars(v,n,i)
        turtle.update()
        
n = 50
v = [0] * n
for i in range(n):
    v[i] = random.randint(1,800)

t1 = time.time()
selection_sort(v,n)
turtle.clear()
draw_bars(v,n,-1)
turtle.update()
t2 = time.time()
print('elapsed time=', t2-t1)

Insertion Sort Animation with Python and Turtle (Source Code Included)

Posted on by

Generate 50 random numbers and draw them as bars. Following the steps of insertion sort algorithm and redraw the bar every single step to show how bubble sort works.

Compare against Bubble Sort. Which is faster?

Source Code:

import turtle
import random
import time

screen = turtle.Screen()
screen.setup(1000,1000)
screen.tracer(0,0)
screen.title('Insertion 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.fillcolor('gray')
    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):
    x = -400
    w = 800/n
    for  i in range(n):
        draw_bar(x,-400,w,v[i])
        x += w

def insert(v,k):
    x = v[k]
    for i in range(k-1,-1,-1):
        if v[i] > x: v[i+1] = v[i]
        else:
            v[i+1] = x
            return
        turtle.clear()
        draw_bars(v,n)
        screen.update()
    v[0] = x
    
def insertion_sort(v,k):
    if k == 1: return
    insertion_sort(v,k-1)
    insert(v,k-1)
    
n = 50
v = [0] * n
for i in range(n):
    v[i] = random.randint(1,800)

t1 = time.time()
insertion_sort(v,n)
t2 = time.time()
print('elapsed time=', t2-t1)

Drawing Sierpinski Pentagon with Chaos Game and Python Turtle (with Solution)

Posted on by

Draw the Sierpinski Pentagon with Chaos Game. Work on this Sierpinski Triangle with Chaos Game first if you haven’t done so already.

Hint: Try jump less than half way to the target.

Sierpinski Pentagon with Chaos Game

Solution:

import turtle
import random
import math

screen = turtle.Screen()
screen.title('Sierpinski Pentagon with Chaos Game - PythonTurtle.Academy')
screen.setup(1000,1000)
screen.setworldcoordinates(-250,-250,250,250)
screen.tracer(0,0)
turtle.hideturtle()
turtle.speed(0)
turtle.up()

m=5
angle = math.pi/2
V = []
for i in range(m):
    p = (400*math.cos(angle),400*math.sin(angle))
    V.append(p)
    angle += math.pi*2/m

for v in V:
    turtle.goto(v)
    turtle.dot('red')

n = 100000 # number of points to draw
p = V[0] # start from first vertex
t = turtle.Turtle()
t.up()
t.hideturtle()
for i in range(n):
    t.goto(p)
    t.dot(2,'orange')
    q = V[random.randrange(len(V))] # pick a random vertex
    p = ((q[0]+p[0])/2.6,(q[1]+p[1])/2.6) # go to mid point between the random vertex and point   
    if i % 1000 == 0: # update for every 1000 moves, this part is for performance reason only
        t = turtle.Turtle() # use new turutle
        t.up()
        t.hideturtle()
        screen.update()

Drawing Sierpinski Carpet with Chaos Game (with Solution)

Posted on by

You can draw a Sierpinski Carpet with Chaos Game too. Read the first Chaos Game project first to understand what Chaos Game is.

In this project, you start with a square. The moving point will toward a randomly chosen corner of the square as well as the center of the four edges of the square. Therefore, there are total eight points that the moving point will move toward. In addition, it will only 1/3 of the way towards the target.

Sierpinski Carpet with Chaos Game

Solution:

import turtle
import random
import math

screen = turtle.Screen()
screen.title('Sierpinski Carpet with Chaos Game - PythonTurtle.Academy')
screen.setup(1000,1000)
screen.setworldcoordinates(-200,-200,200,200)
screen.tracer(0,0)
turtle.hideturtle()
turtle.speed(0)
turtle.up()

m=4
angle = math.pi/4
V = []
for i in range(m):
    p = (400*math.cos(angle),400*math.sin(angle))
    V.append(p)
    angle += math.pi*2/m

for v in V:
    turtle.goto(v)
    turtle.dot('blue')

n = 100000 # number of points to draw
p = V[0] # start from the first vertex
t = turtle.Turtle()
t.up()
t.hideturtle()
for i in range(n):
    t.goto(p)
    t.dot(2,'red')
    r = random.randrange(len(V)) # pick a random vertex
    if random.randint(0,1) == 0: # randomly decide to use edge or vertex
        q = V[r] # vertex
    else:
        q = ((V[r][0]+V[(r+1)%len(V)][0])/2,(V[r][1]+V[(r+1)%len(V)][1])/2) # go to mid point between two vertices   
    p = ((q[0]+p[0])/3,(q[1]+p[1])/3) # go 1/3 towards target   
    if i % 1000 == 0: # update for every 1000 moves, this part is for performance reason only
        t = turtle.Turtle() # use new turutle
        t.up()
        t.hideturtle()
        screen.update()

Restricted Polygon Chaos Game 2 with Python Turtle

Posted on by

In a previous project, you drew a Sierpinski Triangle with Chaos Game. You also did restricted chaos projects for square and pentagon. Now, generalize the project that allows chaos game for polygon of any number of vertices.

In this project, the restriction is: next vertex has to be immediate neighbors of the previous vertex or the same vertex as the previous vertex. This restriction should draw following figures from pentagon to decagon.

Pentagon Fractal with Chaos Game
Hexagon Fractal with Chaos Game
Heptagon Fractal with Chaos Game
Nonagon Fractal with Chaos Game
Decagon Fractal with Chaos Game

Restricted Polygon Chaos Game 1 with Python Turtle

Posted on by

In a previous project, you drew a Sierpinski Triangle with Chaos Game. You also did restricted chaos projects for square and pentagon. Now, generalize the project that allows chaos game for polygon of any number of vertices.

In this project, the restriction is: next vertex cannot be close neighbors of previously chosen vertex. This restriction should draw following figures from pentagon to decagon.

Pentagon Fractal with Chaos Game
Hexagon Fractal with Chaos Game
Heptagon Fractal with Chaos Game
Octagon Fractal with Chaos Game
Nonagon Fractal with Chaos Game
Decagon Fractal with Chaos Game