Animation of sorting algorithms

Question

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[0] += 1
 text.set_text("# of operations: {}".format(iteration[0]))
def create_animation(generator,unordered,n):
 title = 'Sorting Animation'
 fig, ax = plt.subplots() #Creating axis and figure
 ax.set_title(title) #Adding a title
 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 = [0]
 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.length.grid(row=1,column=3,padx=5,pady=5,columnspan=2,ipadx=50)
 self.close_button = Button(master, text="Close", command=master.quit)
 self.close_button.grid(row=1,column=6,padx=5,pady=5)
 self.bubble_sort = Button(master, text="Bubble Sort",command=self.bubble_s)
 self.bubble_sort.grid(row=2,column=1,padx=5,pady=5)
 self.merge_sort = Button(master, text="Merge Sort",command=self.merge_s)
 self.merge_sort.grid(row=2,column=2,padx=5,pady=5)
 self.insertion_sort = Button(master, text="Insertion Sort",command=self.insertion_s)
 self.insertion_sort.grid(row=2,column=3,padx=5,pady=5)
 self.shell_sort = Button(master, text="Shell Sort",command=self.shell_s)
 self.shell_sort.grid(row=2,column=4,padx=5,pady=5)
 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.

Answer 1

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. :)