3D Visualization of Insertion Sort using Matplotlib in Python

3D Visualization of Insertion Sort Using Matplotlib in Python

Sorting algorithms are fundamental in computer science, and understanding their behavior can be challenging. Visualizing these algorithms can make the learning process more intuitive. In this article, we'll explore how to animate the Insertion Sort algorithm using Python's Matplotlib library, providing a clear and engaging way to grasp its mechanics.

What Is Insertion Sort?

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much like sorting playing cards in your hands. The algorithm divides the input list into two parts: a sorted part and an unsorted part. It picks elements from the unsorted part and places them at the correct position in the sorted part. This process is repeated until the entire list is sorted. Insertion Sort is efficient for small data sets or nearly sorted data but has a time complexity of O(n²) in the average and worst cases.

Setting Up the Environment

Before we begin, ensure you have Python installed along with the necessary libraries. You'll need:

pip install numpy matplotlib

These libraries will help us generate the data and create the animations.

Implementing Insertion Sort with Visualization

We'll create a function to perform Insertion Sort and record the state of the list after each insertion. This allows us to visualize the sorting process step by step.

import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
import random

def insertionsort(a):
    for j in range(1, len(a)):
        key = a[j]
        i = j - 1
        while i >= 0 and a[i] > key:
            a[i + 1] = a[i]
            i -= 1
            yield a
        a[i + 1] = key
        yield a

def visualize_insertion_sort():
    n = 11
    a = [i for i in range(1, n + 1)]
    random.shuffle(a)

    fig = plt.figure()
    ax = fig.add_subplot(111, projection='3d')
    ax.set_xlabel('Index')
    ax.set_ylabel('Step')
    ax.set_zlabel('Value')

    def update_bars(arr, step, ax):
        ax.clear()
        ax.bar(range(len(arr)), arr, zs=step, zdir='y', alpha=0.8)
        ax.set_xlabel('Index')
        ax.set_ylabel('Step')
        ax.set_zlabel('Value')
        ax.set_yticks([])

    steps = insertionsort(a)
    for i, step in enumerate(steps):
        update_bars(step, i, ax)
    plt.show()

visualize_insertion_sort()

This code creates a 3D bar chart that updates with each frame, showing the progression of the Insertion Sort algorithm.

Enhancing the Visualization

To make the visualization more informative, you can add labels to indicate the number of operations performed and highlight the elements being compared or swapped. This provides a clearer understanding of the algorithm's behavior at each step.

Conclusion

Visualizing algorithms like Insertion Sort can significantly enhance your understanding of their operations. By animating the sorting process, you can observe how the algorithm progresses and how elements are moved, making the learning experience more engaging and effective.