Build a Sorting Visualizer in Python
Tags: python, beginners
Published: 2020-06-07 10:30:53

# **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. 

<img src="https://dev-to-uploads.s3.amazonaws.com/i/mvw1cfitt7s1y31gsjk0.png">

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:
```python
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](https://www.geeksforgeeks.org/selection-sort/)
```python
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](https://www.geeksforgeeks.org/bubble-sort/)
```python
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](https://www.geeksforgeeks.org/insertion-sort/)
```python
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](https://www.geeksforgeeks.org/merge-sort/)
```python
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](https://www.geeksforgeeks.org/quick-sort/)
```python
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.
```python
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*](https://www.pygame.org/docs/) 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.

<img src="https://dev-to-uploads.s3.amazonaws.com/i/vr9cio5ds2vlkd5gflm9.png">

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`

<img src="https://dev-to-uploads.s3.amazonaws.com/i/981n5ch7v6wtpojkvbim.png">

<img src="https://dev-to-uploads.s3.amazonaws.com/i/kqgwk34467g1ion6ai3v.png">

<img src="https://dev-to-uploads.s3.amazonaws.com/i/sg6aakwxkkw0qf1uuqay.png">

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](https://www.linkedin.com/in/k-g-prajwal-a6b3b517a/). The code is available on my [GitHub](https://github.com/K-G-PRAJWAL/Python-Projects/tree/master/Sorting%20Visualizer).


#### *Thank You!*