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 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