# Animation of sorting algorithms

I have created a visualisation of sorting algorithms using tkinter and matplotlib. Please let me know what you think and if you have any suggestions or find errors. The aim of this code is to create a GUI in which the user can enter a length for a random array of number, then select a sorting algorithm from a button, which brings up an animated plot of the sorting algorithm being used on the random array. The plot uses bar heights to represent the numbers in the array. The project can be found with the algorithms separated for ease of reading at: https://github.com/MGedney1/Sorting_Algorithm_Visualisation

Code:


import random
import time
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from matplotlib.figure import Figure
from matplotlib import style
style.use('ggplot')
from tkinter import Tk,Label,Entry,Button

def bubble_sort(lst):        #Bubble Sort
index = len(lst) - 1
while index >= 0:
test_index = index
while test_index >= 0:
if lst[index] < lst[test_index]:
temp = lst[index]
lst[index] = lst[test_index]
lst[test_index] = temp
test_index -= 1
yield lst
index -= 1

def merge_sort(lst, start, end):        #Merge sort

if end <= start:
return

mid = start + ((end - start + 1) // 2) - 1      #Finding mid point for split
yield from merge_sort(lst, start, mid)        #Further splitting first half
yield from merge_sort(lst, mid + 1, end)      #Further splitting second half
yield from merge(lst, start, mid, end)        #Merging
yield lst

def merge(lst, start, mid, end):

result = []
leftIdx = start
rightIdx = mid + 1

while leftIdx <= mid and rightIdx <= end:       #checking if next index of first or second list is larger and appending to the result list
if lst[leftIdx] < lst[rightIdx]:
result.append(lst[leftIdx])
leftIdx += 1
else:
result.append(lst[rightIdx])
rightIdx += 1

while leftIdx <= mid:       #If only first list filled then appending that to result
result.append(lst[leftIdx])
leftIdx += 1

while rightIdx <= end:      #Vice versa for the second list
result.append(lst[rightIdx])
rightIdx += 1

for i, sorted_val in enumerate(result):     #Copying values and order to the origional array
lst[start + i] = sorted_val
yield lst

def insertion_sort(lst):
for i in range(1,len(lst)):
j = i-1     #Starting comparison to just the first element of the list
next_element = lst[i]       #Iterating through the test values from start (indexed 1 intially) to insert
while (lst[j] > next_element) and (j >= 0):     #iterating through each element already ordered to find position of test value
lst[j+1] = lst[j]
j -= 1
lst[j+1] = next_element
yield lst

def shell_sort(lst):

split_point = len(lst) // 2     #Initially splitting the list in half
while split_point > 0:

for i in range(split_point, len(lst)):
temp = lst[i]
j = i

while j >= split_point and lst[j - split_point] > temp:     #Sorting the subsection of the list
lst[j] = lst[j - split_point]
j = j - split_point
lst[j] = temp

split_point = split_point // 2      #splitting the unordered part of the list in half
yield lst

def create_array(n):

unordered = [i + 1 for i in range(n)]       #Creating a list of subsequent values
random.seed(time.time())
random.shuffle(unordered)       #Shuffling the list

return unordered

def update_fig(unordered, rects, iteration,text):        #Update fig function
for rect, val in zip(rects, unordered):     #Setting height of the rectangles
rect.set_height(val)
iteration += 1
text.set_text("# of operations: {}".format(iteration))

def create_animation(generator,unordered,n):
title = 'Sorting Animation'

fig, ax = plt.subplots()        #Creating axis and figure

bar_rects = ax.bar(range(len(unordered)), unordered, align="edge")      #Creating the rectangular bars

ax.set_xlim(0, n)       #Axis limits
ax.set_ylim(0, int(1.07 * n))

text = ax.text(0.02, 0.95, "", transform=ax.transAxes)      #Number of operations counter

iteration = 

if generator != merge_sort:
anim = animation.FuncAnimation(fig, func=update_fig,        #Creating the animation
fargs=(bar_rects, iteration,text), frames=generator(unordered), interval=1,
repeat=False)
else:
anim = animation.FuncAnimation(fig, func=update_fig,        #Creating the animation for merge sort
fargs=(bar_rects, iteration,text), frames=generator(unordered,0,n-1), interval=1,
repeat=False)

plt.show()      #Showing the plot

class GUI:
def __init__(self,master):
self.master = master
master.title('Sorting Algorithm Visualisation')

self.instruct = Label(master, text="Please enter a length for the array to sort: ")
self.instruct.grid(row = 1, column = 1,columnspan=2,ipadx=50)

self.length = Entry(master)

self.close_button = Button(master, text="Close", command=master.quit)

self.bubble_sort = Button(master, text="Bubble Sort",command=self.bubble_s)

self.merge_sort = Button(master, text="Merge Sort",command=self.merge_s)

self.insertion_sort = Button(master, text="Insertion Sort",command=self.insertion_s)

self.shell_sort = Button(master, text="Shell Sort",command=self.shell_s)

def get_length(self):
self.n = int(self.length.get())

def bubble_s(self):
self.animate(bubble_sort)

def merge_s(self):
self.animate(merge_sort)

def insertion_s(self):
self.animate(insertion_sort)

def shell_s(self):
self.animate(shell_sort)

def animate(self,generator):
self.get_length()
unordered = create_array(self.n)
create_animation(generator,unordered,self.n)

if __name__ == '__main__':
root = Tk()
gui = GUI(root)
root.mainloop()


• Add some information what that code is actually intended to do please. – πάντα ῥεῖ Jan 7 at 20:03

I'll just review bubble_sort as an example. My quick notes:

1. Add a useful docstring and/or types (I had to read the entire function to realize that it was a generator)
2. When iterating over a range, use for in range rather than while. I also prefer using brief, generic variable names like i and j in lieu of names like index and test_index that are longer without being any more descriptive.
3. You can swap two elements with a tuple assignment.
from typing import Generator, List, TypeVar

_Elem = TypeVar('_Elem')

def bubble_sort(elems: List[_Elem]) -> Generator[List[_Elem]]:
"""Bubble-sort a list, yielding the list at each swap."""
for i in list(reversed(range(len(elems)))):
for j in list(reversed(range(i))):
if elems[i] < elems[j]:
elems[i], elems[j] = elems[j], elems[i]
yield elems


Note that if you iterate forward instead of backward, you can just use for i in range(len(elems)) -- simply making the code easier to read might be a good enough reason to rearrange this. :)