3D Visualization of Quick Sort using Matplotlib in Python

3D Visualization of Quick 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 Quick Sort algorithm using Python's Matplotlib library, providing a clear and engaging way to grasp its mechanics.

What Is Quick Sort?

Quick Sort is a divide-and-conquer algorithm that selects a pivot element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. This approach ensures that the algorithm runs in O(n log n) time on average, making it efficient for large datasets. However, its worst-case time complexity is O(n²), which can occur when the pivot selection is poor.

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 Quick Sort with Visualization

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

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

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        yield arr
        yield from quicksort(arr, low, pi - 1)
        yield from quicksort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def visualize_quick_sort():
    arr = np.random.randint(1, 100, 20)
    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 = quicksort(arr.copy(), 0, len(arr) - 1)
    for i, step in enumerate(steps):
        update_bars(step, i, ax)
    plt.show()

visualize_quick_sort()

This code creates a 3D bar chart that updates with each frame, showing the progression of the Quick 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 Quick 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.