Visualization for a common sorting algorithm - Bubble Sort

Background

In a Computer Science class being taught at my high school, I came across the concept of sorting. Sorting plays a crucial role in several applications and I realized in that class that there are different ways in which a typical sorting operation could be implemented. Having a variety of implementation could be useful when dealing with tasks that have limited memory capacity and need optimal execution speed. However, one thing that my peers and I struggled alot with was visualizing the algorithm written on the blackboard. That's when I had the idea for implementing a soritng visualizer and picked a simple Bubble Sort Algorithm to try my implementation out!

Proposed Solution

For developing a good sorting visualizer, I started looking for good Python libraries for visualization. The modules I found that would be useful for the project were:

• Matplotlib: An excellent library for visualizing Python arrays. To install the module, we could use the following command in the terminal: pip install matplotlib
• PyQt5: Another great Python library for developing interactive desktop applications. To install the module, we could use the following command in the terminal: pip install PyQt5==5.9.2

Coding!

Next step involved creating a main.py file and writing the code for bubblesort algorithm. Next step involved using the above libraries to visualize the algorithm.

Code

The code for my implementation is shown as follows:

    
# imports 
import random 
from matplotlib import pyplot as plt, animation 

# helper methods 
def swap(A, i, j): 
  A[i], A[j] = A[j], A[i] 


# algorithms 
def bubblesort(A): 
  swapped = True
  
  for i in range(len(A) - 1): 
    if not swapped: 
      return
    swapped = False
    
    for j in range(len(A) - 1 - i): 
      if A[j] > A[j + 1]: 
        swap(A, j, j + 1) 
        swapped = True
      yield A 


def visualize(): 
  N = 30
  A = list(range(1, N + 1)) 
  random.shuffle(A) 
  
  # creates a generator object containing all 
  # the states of the array while performing 
  # sorting algorithm 
  generator = bubblesort(A) 
  
  # creates a figure and subsequent subplots 
  fig, ax = plt.subplots() 
  ax.set_title("Bubble Sort O(n\N{SUPERSCRIPT TWO})") 
  bar_sub = ax.bar(range(len(A)), A, align="edge") 
  
  # sets the maximum limit for the x-axis 
  ax.set_xlim(0, N) 
  text = ax.text(0.02, 0.95, "", transform=ax.transAxes) 
  iteration = [0] 
  
  # helper function to update each frame in plot 
  def update(A, rects, iteration): 
    for rect, val in zip(rects, A): 
      rect.set_height(val) 
    iteration[0] += 1
    text.set_text(f"# of operations: {iteration[0]}") 

  # creating animation object for rendering the iteration 
  anim = animation.FuncAnimation( 
    fig, 
    func=update, 
    fargs=(bar_sub, iteration), 
    frames=generator, 
    repeat=True, 
    blit=False, 
    interval=15, 
    save_count=90000, 
  ) 
  
  # for showing the animation on screen 
  plt.show() 
  plt.close() 


if __name__ == "__main__": 
  visualize() 


    

Impact of the solution

After obtaining a working model of the visualizer, I showcased the project to several high school students during Symposiums for evoking their interest in Computer Science. This implementation is currently being used by Girls Coding club for teaching Computer Science concepts to high school girls.