Build a Sorting Visualizer in Python

#python #beginners

Python

Python programming language has been dominating the field of computer science recently with its applications in many areas such as machine learning, data science, artificial intelligence, web development and software programming which are the recent trends of the 21st century. According to PYPL PopularitY of programming language index, python has about 31.6% of the total share compared to other programming languages.

So, I guess we could learn python in the best way possible, by building an amazing project to master one of the fundamentals in any programming language - Sorting.
By the end of this article you would have built an amazing sorting visualizer using five different algorithms:

Selection Sort
Bubble Sort
Insertion Sort
Merge Sort
Quick Sort

Algorithms

Let's create a file called algorithms.py and in that, we will write all the sorting algorithms in python. Import the time module to inform the user about the time taken by the visualizer (Note: The time that will be displayed is the time taken by our system to render the visualizer and has no relevance to the sorting algorithm).
Create a class called Algorithm and paste this piece of code in there:



class Algorithm:
    def __init__(self, name):
        self.array = random.sample(range(512), 512) # Random array of size 512
        self.name = name # Get name of the variable

    def update_display(self, swap1=None, swap2=None):
        import visualizer
        visualizer.update(self, swap1, swap2) # pass the indexes to be swapped into the visualizer

    def run(self): # Start the timer and run the algorithm
        self.start_time = time.time() 
        self.algorithm()
        time_elapsed = time.time() - self.start_time
        return self.array, time_elapsed

We will initially create a random array of size 512. In the update_display method we will call the update function in visualizer.py which we will write later to handle the graphics. Finally, the run method will start the timer and call the algorithm function which is a part of every sorting algorithm to come. It returns the sorted array and the elapsed time.

Selection Sort



class SelectionSort(Algorithm):
    def __init__(self):
        super().__init__("SelectionSort")

    def algorithm(self):
        for i in range(len(self.array)):
            min_idx = i
            for j in range(i+1, len(self.array)):
                if self.array[j] < self.array[min_idx]:
                    min_idx = j
            self.array[i], self.array[min_idx] = self.array[min_idx], self.array[i]
            self.update_display(self.array[i], self.array[min_idx])

The SelectionSort class will inherit the Algorithm class and in its algorithm method we implement Selection sort. Every time the array updates we continuously call the update_display method and render the sorting of the array realtime. Similarly, we implement likewise to all the other algorithms as well.

Bubble Sort



class BubbleSort(Algorithm):
    def __init__(self):
        super().__init__("BubbleSort")

    def algorithm(self):
        for i in range(len(self.array)):
            for j in range(len(self.array)-1-i):
                if self.array[j] > self.array[j+1]:
                    self.array[j], self.array[j+1] = self.array[j+1], self.array[j]
            self.update_display(self.array[j], self.array[j+1])

Insertion Sort



class InsertionSort(Algorithm):
    def __init__(self):
        super().__init__("InsertionSort")

    def algorithm(self):
        for i in range(len(self.array)):
            cursor = self.array[i]
            idx = i
            while idx > 0 and self.array[idx-1] > cursor:
                self.array[idx] = self.array[idx-1]
                idx -= 1
            self.array[idx] = cursor
            self.update_display(self.array[idx], self.array[i])

Merge Sort



class MergeSort(Algorithm):
    def __init__(self):
        super().__init__("MergeSort")

    def algorithm(self, array=[]):
        if array == []:
            array = self.array
        if len(array) < 2:
            return array
        mid = len(array) // 2
        left = self.algorithm(array[:mid])
        right = self.algorithm(array[mid:])
        return self.merge(left, right)

    def merge(self, left, right):
        result = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
            self.update_display()
        result += left[i:]
        result += right[j:]
        self.array = result
        self.update_display()
        return result

Quick Sort



class QuickSort(Algorithm):
    def __init__(self):
        super().__init__("QuickSort")

    def algorithm(self, array=[], start=0, end=0):
        if array == []:
            array = self.array
            end = len(array) - 1
        if start < end:
            pivot = self.partition(array,start,end)
            self.algorithm(array,start,pivot-1)
            self.algorithm(array,pivot+1,end)

    def partition(self, array, start, end):
        x = array[end]
        i = start-1
        for j in range(start, end+1, 1):
            if array[j] <= x:
                i += 1
                if i < j:
                    array[i], array[j] = array[j], array[i]
                    self.update_display(array[i], array[j])
        return i

Visualizer

Congratulations! You just wrote all the popular sorting algorithms. The final step is to visually display the way how each of these sorting algorithms work.

Here is the code for visualizer.py file.



import algorithms
import time
import os
import sys
import pygame

 # Set the window length and breadth  (Make sure that the breadth is equal to size of array. [512])
dimensions = [1024, 512]
# List all the algorithms available in the project in dictionary and call the necessary functions from algorithms.py
algorithms = {"SelectionSort": algorithms.SelectionSort(), "BubbleSort": algorithms.BubbleSort(), "InsertionSort": algorithms.InsertionSort(), "MergeSort": algorithms.MergeSort(), "QuickSort": algorithms.QuickSort()}

# Check list of all the available sorting techniques using 'list'
if len(sys.argv) > 1:
    if sys.argv[1] == "list":
        for key in algorithms.keys(): print(key, end=" ") # Display the available algorithms
        print("")
        sys.exit(0)

# Initalise the pygame library
pygame.init()
# Set the dimensions of the window and display it
display = pygame.display.set_mode((dimensions[0], dimensions[1]))
# Fill the window with purple hue
display.fill(pygame.Color("#a48be0"))

def check_events(): # Check if the pygame window was quit
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit();
            sys.exit();

def update(algorithm, swap1=None, swap2=None, display=display): # The function responsible for drawing the sorted array on each iteration
    display.fill(pygame.Color("#a48be0"))
    pygame.display.set_caption("Sorting Visualizer     Algorithm: {}     Time: {:.3f}      Status: Sorting...".format(algorithm.name, time.time() - algorithm.start_time)) # Display on title bar
    k = int(dimensions[0]/len(algorithm.array))
    for i in range(len(algorithm.array)):
        colour = (80, 0, 255)
        if swap1 == algorithm.array[i]:
            colour = (0,255,0)
        elif swap2 == algorithm.array[i]:
            colour = (255,0,0)
        # The most important step that renders the rectangles to the screen that gets sorted.
        # pygame.draw.rect(dsiplay_window, color_of_rectangle, size_of_rectangle)
        pygame.draw.rect(display, colour, (i*k,dimensions[1],k,-algorithm.array[i]))
    check_events()
    pygame.display.update()

def keep_open(algorithm, display, time): # Keep the window open until sort completion
    pygame.display.set_caption("Sorting Visualizer     Algorithm: {}     Time: {:.3f}      Status: Done!".format(algorithm.name, time))
    while True:
        check_events()
        pygame.display.update()

def main():
    if len(sys.argv) < 2:
        print("Please select a sorting algorithm.") 
    else:
        try:
            algorithm = algorithms[sys.argv[1]] # Pass the algorithm selected
            try:
                time_elapsed = algorithm.run()[1]
                keep_open(algorithm, display, time_elapsed)
                pass
            except:
                pass
        except:
            print("Error.")

if __name__ == "__main__":
    main()

Yes! I know, its a lot of code to digest, but I assure you that it will all be fruitful when you hit the run button on this project. Meanwhile, let me explain the visualizer code to you.

Firstly, we import the algorithms python file where we wrote our algorithms. Then, import pygame module in python to work with graphics in our project.
Also, install pygame by executing pip install pygame in your terminal.
Set the window size in dimensions array and make sure to leave the second parameter 512, as that is the number of random samples we are using.
The next few lines of commands are to display the list of available algorithms to the user and prompt them to choose one and enter it while running our code.
Then, initialize the pygame module, set the dimensions of the window and fill the display with a colour.
The check_events function is to exit out of the program in case the window is closed.
Then there is the most important function in the entire program - update method. This method takes in the array after every iteration, and the two swapping variables at hand, swap1 and swap2 variables. These variables are assigned different colours.
Then we use the pygame.draw.rect() function to render those array elements to the window and update it.
The keep_open function keeps the pygame window open as long as it is running and the window hasn't been terminated.
Finally, the main function takes in the user-selected algorithm as input and calls the specific algorithm along with its timer.

Result

Ultimately, the time has come to run our project. Open up your terminal in the project directory and execute python visualizer.py list to obtain the list of all available algorithms.

Then execute python visualizer.py <sorting-algorithm>
Where, sorting-algorithm is one of the algorithms mentioned in the list.

For example,
python visualizer.py SelectionSort

I hope you enjoyed working on this project and at the same time learnt a few sorting algorithms in python. For any queries feel free to contact me on my LinkedIn. The code is available on my GitHub.