I'm a beginner Python learner and trying to implement Sorting Algorithm Visualizer as a project. I have implemented Selection Sort, Insertion Sort and Bubble Sort. They are correctly visualizing their algorithms I think. But in Merge Sort, I had some issues about visualizing and I can't figure out what's wrong with my code. Algorithm works well but I could not visualize it correctly.
Here is my Visualizer and Block classes. Block represents each element of the list as a Turtle object.
from blocks import Block
from turtle import *
import time
class Visualize():
START_X = -650
blocks = []
@classmethod
def create_screen(cls):
cls.screen = Screen()
cls.screen.title('Sorting Algorithms')
cls.screen.setup(width=1600, height=900, starty=0)
cls.screen.bgcolor('black')
cls.screen.tracer(0)
@classmethod
def show_list(cls, arr):
for i in range(len(arr)):
cls.blocks.append(Block(len_coef=arr[i], xcor=(cls.START_X + 15 * i)))
cls.screen.update()
@classmethod
def selection_sort(cls, arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
cls.blocks[j].color('red')
cls.screen.update()
time.sleep(0.02)
if arr[j] < arr[min_index]:
min_index = j
cls.blocks[j].color('white')
arr[min_index], arr[i] = arr[i], arr[min_index]
cls.blocks[min_index], cls.blocks[i] = cls.blocks[i], cls.blocks[min_index]
cls.blocks[min_index].setx(cls.START_X + 15 * min_index)
cls.blocks[i].setx(cls.START_X + 15 * i)
cls.screen.update()
@classmethod
def insertion_sort(cls, arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
block_key = cls.blocks[i]
block_key.color('red')
cls.screen.update()
j = i - 1
while j >= 0 and key < arr[j]:
cls.blocks[j].setx(cls.START_X + 15 * (j + 1))
cls.blocks[j + 1].setx(cls.START_X + 15 * j)
cls.blocks[j], cls.blocks[j + 1] = cls.blocks[j + 1], cls.blocks[j]
cls.screen.update()
time.sleep(0.02)
arr[j + 1] = arr[j]
j -= 1
block_key.color('white')
arr[j + 1] = key
@classmethod
def bubble_sort(cls, arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
cls.blocks[j].color('red')
cls.screen.update()
time.sleep(0.02)
if arr[j] > arr[j + 1]:
cls.blocks[j].setx(cls.START_X + 15 * (j + 1))
cls.blocks[j + 1].setx(cls.START_X + 15 * j)
cls.blocks[j], cls.blocks[j + 1] = cls.blocks[j + 1], cls.blocks[j]
arr[j], arr[j + 1] = arr[j + 1], arr[j]
cls.blocks[j + 1].color('white')
else:
cls.blocks[j].color('white')
cls.screen.update()
@classmethod
def merge_sort(cls, arr):
n = len(arr)
if n > 1:
mid = n // 2
L = arr[:mid]
R = arr[mid:]
L_BLOCKS = cls.blocks[:mid]
R_BLOCKS = cls.blocks[mid:]
cls.merge_sort(L)
cls.merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
L_BLOCKS[i].color('red')
cls.screen.update()
time.sleep(0.05)
L_BLOCKS[i].setx(cls.START_X + 15 * k)
L_BLOCKS[i].color('white')
cls.blocks[k] = L_BLOCKS[i]
arr[k] = L[i]
i += 1
else:
R_BLOCKS[j].color('red')
cls.screen.update()
time.sleep(0.05)
R_BLOCKS[j].setx(cls.START_X + 15 * k)
R_BLOCKS[j].color('white')
cls.blocks[k] = R_BLOCKS[j]
arr[k] = R[j]
j += 1
cls.screen.update()
k += 1
while i < len(L):
L_BLOCKS[i].color('red')
cls.screen.update()
time.sleep(0.05)
L_BLOCKS[i].setx(cls.START_X + 15 * k)
L_BLOCKS[i].color('white')
cls.blocks[k] = L_BLOCKS[i]
arr[k] = L[i]
i += 1
k += 1
cls.screen.update()
while j < len(R):
R_BLOCKS[j].color('red')
cls.screen.update()
time.sleep(0.05)
R_BLOCKS[j].setx(cls.START_X + 15 * k)
R_BLOCKS[j].color('white')
cls.blocks[k] = R_BLOCKS[j]
arr[k] = R[j]
j += 1
k += 1
cls.screen.update()
from turtle import *
TURTLE_SIZE = 20
STRETCH_COEF = 0.5
class Block(Turtle):
def __init__(self, len_coef, xcor):
super().__init__()
self.setheading(90)
self.shape('square')
self.shapesize(stretch_len=STRETCH_COEF + (STRETCH_COEF * len_coef), stretch_wid=0.5)
self.turtle_length, self.turtle_width = ((TURTLE_SIZE * STRETCH_COEF * len_coef), TURTLE_SIZE)
self.goto(xcor, (-430 + self.turtle_length / 2))
self.color('white')
self.penup()
I have treated blocks the same way I did to arrays in every algorithm. So tried it on Merge Sort too but it does not correctly sorting the list in the Visualization. The code might be weirdly or bad designed. Also advices for that would be great!
I believe are two issues with the code. The first issue is that the array of values being sorted gets decoupled from the array of turtles that represent the values. You pass the array of values to be sorted but assume they are still associated with the array of turtles index-wise but this isn't the case. To fix this, I bound the two together and sort them as a unit.
The second issue is you don't maintain a concept of absolute position within the turtles, so you end up doing all the subprocessing on a slice of the left most turtles rather then the equivalent location in the values array. We need to pass an offset down the recursion stack to indicate what the the turtle array indexes are relative to so we're moving the correct turtles.
from turtle import Screen, Turtle
from time import sleep
TURTLE_SIZE = 20
STRETCH_COEF = 0.5
VALUE, BLOCK = 0, 1
class Block(Turtle):
def __init__(self, len_coef, xcor):
super().__init__()
self.setheading(90)
self.shape('square')
self.shapesize(stretch_len=STRETCH_COEF + STRETCH_COEF * len_coef, stretch_wid=0.5)
turtle_length = TURTLE_SIZE * STRETCH_COEF * len_coef
self.goto(xcor, turtle_length/2 - 430)
self.color('white')
self.penup()
class Visualize():
START_X = -650
blocks = []
@classmethod
def create_screen(cls):
cls.screen = Screen()
cls.screen.title('Sorting Algorithms')
cls.screen.setup(width=1600, height=900, starty=0)
cls.screen.bgcolor('black')
cls.screen.tracer(0)
return cls.screen
@classmethod
def show_list(cls, arr):
for i, value in enumerate(arr):
cls.blocks.append(Block(len_coef=value, xcor=(cls.START_X + 15 * i)))
cls.screen.update()
@classmethod
def merge_sort(cls, arr, offset=0):
n = len(arr)
if n <= 1:
return
mid = n // 2
L = list(zip(arr[:mid], cls.blocks[offset:offset + mid]))
R = list(zip(arr[mid:], cls.blocks[offset + mid:offset + n]))
cls.merge_sort(L, offset)
cls.merge_sort(R, offset + mid)
i = j = k = 0
while k < n:
if not (j < len(R)) or i < len(L) and L[i][VALUE] < R[j][VALUE]:
L[i][1].color('red')
cls.blocks[k + offset] = L[i][BLOCK]
arr[k] = L[i][VALUE]
i += 1
# elif not (i < len(L)) or j < len(R) and not L[i][VALUE] < R[j][VALUE]:
else:
R[j][1].color('red')
cls.blocks[k + offset] = R[j][BLOCK]
arr[k] = R[j][VALUE]
j += 1
cls.screen.update()
sleep(0.02)
cls.blocks[k + offset].setx(cls.START_X + 15 * (k + offset))
cls.blocks[k + offset].color('white')
cls.screen.update()
k += 1
if __name__ == '__main__':
from random import sample
array = sample(range(85), 75)
screen = Visualize.create_screen()
Visualize.show_list(array)
Visualize.merge_sort(array)
print(array)
screen.exitonclick()
I made other changes like making the conditions more complex in order to move redundant after merge code into the main merge code.