3D Visualisation of Quick Sort using Matplotlib in Python

A popular and effective sorting algorithm called Quick Sort uses a divide-and-conquer approach to organize the items in a list or array. Although Quick Sort is commonly implemented as a text-based algorithm, you may use Python's Matplotlib to visualize the method in three dimensions to better understand how it functions.

This visualization adds a third dimension to the conventional two-dimensional representations of the sorting process by allowing you to visualize it in three dimensions. An overview of how to do this is provided below:

By examining and comparing the number of operations required to compare and swap the pieces, visualizing algorithms helps one better comprehend them. Since 3D algorithm visualization is less frequent, we'll use Matplotlib to plot bar graphs and animate them to represent the array's members.

Data Representation: Create a 3D scatter plot to first depict your list or array. Each data point is a 3D coordinate, with the x-axis denoting the element's index, the y-axis denoting its value, and the z-axis initially set to a fixed value (for example, zero).

Partitioning: The primary operation of Quick Sort is partitioning, which involves choosing a pivot element and moving the other elements so that all of those smaller than the pivot are on one side and all of those larger than the pivot are on the other. Moving the pivot element up and down the y-axis as the data points are moved along the x-axis allows you to animate this process in your 3D visualization.

Recursion: Recursive algorithms are used in Quick Sort. Each recursive call that the algorithm makes can be visualized in your visualization as a separate 3D scatter plot as the program continues. This makes it easier to understand how the algorithm divides the problem into smaller problems.

Let's look at the Quick Sort 3D Visualisations:

Approach:

We'll create an array that contains random elements.
For reasons of visualization, the yield statement will be used in place of the return statement when the algorithm is applied to that array.
Following comparison and swapping, the array's current states will be produced. So, a generator object will be returned by the process.
We will illustrate comparing and switching of the array using Matplotlib animation.
The graph will then be plotted, returning a Poly3dCollection object for use in subsequent animation.

Implementation

# Importing all required  modules
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from mpl_toolkits.mplot3d import axes3d
import matplotlib as mp
import numpy as np
import random
# quicksort function
def quicksort(a, l, r):
    if l>=r:
        return
    x=a[l]
    j=l
    for i in range(l+1, r+1):
        if a[i]<=x:
            j+=1
            a[j], a[i] = a[i], a[j]
        yield a
    a[l], a[j]=a[j], a[l]
    yield a 
    # The array is produced by the yield from the statement after division.
    yield from quicksort(a, l, j-1)
    yield from quicksort(a, j+1, r) 
# function to plot bars
def showGraph():   
    # for distinct random values
    n=int(input("enter array size\n"))
    a=[i for i in range(1, n+1)]
    random.shuffle(a)
    datasetName='Random'     
    # The function returned the generator object.
    generator = quicksort(a, 0, n-1)     
    algoName='Quick Sort'     
    # style of the chart
    plt. style.use('fivethirtyeight')     
    # set the bars' colors
    data_normalizer = mp. colors.Normalize() 
    color_map = mp. colors.LinearSegmentedColormap(
        "my_map",
        {
            "red": [(0, 1.0, 1.0),
                    (1.0, .5, .5)],
            "green": [(0, 0.5, 0.5),
                      (1.0, 0, 0)],
            "blue": [(0, 0.50, 0.5),
                     (1.0, 0, 0)]
        }
    )
 
    fig = plt.figure()
    ax = fig.add_subplot(projection='3d')
    # the bars' z values and locations
    z = np.zeros(n)
    dx = np.ones(n)
    dy = np.ones(n)  
    dz = [i for i in range(len(a))]
    #  was returned by Poly3dCollection into a variable called rects.
    rects = ax.bar3d(range(len(a)), a, z, dx,
                     dy, dz,
                     color = color_map(data_normalizer(range(n))))
    # Setting the array's length as the maximum value for the x and y limits
    ax.set_xlim(0, len(a))
    ax.set_ylim(0, int(1.1*len(a))) 
    ax.set_title("ALGORITHM : "+algoName+"\n"+"DATA SET : "+datasetName,
                 fontdict={'fontsize': 13, 'fontweight': 'medium',
                           'color': '#E4365D'})
    # Adding text to the chart
    text = ax.text2D(0.1,0.95, "", horizontalalignment = 'center',
                     verticalalignment = 'center',
                     transform=ax.transAxes,
                     color = "#E4365D")
    iteration = [0]
    # to call the animation function repeatedly
    def animate(A, rects, iteration):
        # to remove the bars from the object in the Poly3DCollection
        ax.collections.clear()
        ax.bar3d(range(len(a)), A, z, dx,
                 dy, dz,
                 color = color_map(data_normalizer(range(n))))
        iteration[0] += 1
        text.set_text("iterations : {}".format(iteration[0]))         
    # Here, the animate function is invoked and the generator object is supplied.
    anim = FuncAnimation(fig, func=animate,
        fargs = (rects, iteration),
       frames = generator, interval=50,
        repeat=False)     
    # showing the plot
    plt.show() 
# function call
showGraph()

Output: