Sorting out Sorting in 16 Shots with an LLM

In an homage to the seminal computer animation, "Sorting out Sorting" by Ronald M. Baecker and David Sherman at  University of Toronto, presented at SIGGRAPH 1981, this present day retrospective embarked on a man-machine collaboration to revisit the concept with modern LLM technology. To complete this "quick-hack" nod to the original, ChatGPT-4, was employed to illuminate the intricacies of sorting algorithms through a Python demonstration that was built and run for multiple cases in an evening - a much shorter period of time that coding this from scratch, for this author anyway.

In the end, this collaboration focused on four sorting algorithms: quicksort, bubblesort, insertion sort, and selection sort. Each algorithm was animated to showcase its operational nuances and performance implications, dependent on the array size.

The exploration spanned various case studies, from sorting four items to the challenge of a forty-item array. These cases illustrated the performance scalability of each algorithm, reinforcing the importance of algorithm choice based on data size and structure.

The effort culminated in a Python-based animation, refined across 16 shots to aid clarity, accuracy, and pedagogical value. This man-machine collaboration with ChatGPT-4 underscores the synergy between human expertise and artificial intelligence in computer science education.

For those intrigued by the nuances of algorithm efficiency and the visual pedagogy of sorting, this quick project serves as a testament to the enduring relevance of the original "Sorting out Sorting" and the evolutionary journey of computational teaching tools and the technology that drives them.

Results:

Note the number of steps that each sort took for each of the size-item cases:

1) The four-item case:

2) The five-item case:

3) The ten-item case:

4) The twenty item case:

5) The forty item case:

Observations
Notice the relatively poor performance of quicksort relative to the other sorts for small numbers of items and the relatively good performance of selection sort.


TLDR;

Parallel attempts were made using ChatGPT-3.5 and Claude3-Opus, but these fell short of expectations, so the author used ChatGPT-4 to execute a brief exploration of sorting algorithms. The conversation that led to acceptable code required16 iterative chat laps outlined for those who are coding with Large Language Models (LLMs) as follows:

1. Initial Request: Asked for a Python demo to animate sorting with a comparison of quicksort and bubblesort in Jupyter Notebook using Google Colab.
2. Clarification and Correction: Adjustments were made to increase the array size, which caused an IndexError.
3. Fix for IndexError: Provided a solution to fix the IndexError related to the array size increase.
4. Background Color Adjustment: You requested changing the graph background to your trademark color and further adjustments.
5. Sorting Algorithm and Layout Update: Requested adding mergesort to the comparison and faced an execution error.
6. Alternative Sorting Algorithm: Suggested using insertion sort as an easier alternative for visualization.
7. Visualization Enhancement: Added detailed visualization for tracking the sorting process with colors.
8. Error Handling: Addressed an IndexError related to indexing issues in the updated visualization code.
9. Additional Sorting Algorithm and Grid Layout: Included a fourth sorting algorithm and updated the layout to a 2x2 grid.
10. Visual Tracking Features: Requested marking special elements (pivot, etc.) with specific colors for clarity, this was successful, though quite complex to track.
11. Step Annotations Missing: Noted that step annotations were dropped from the visualization.
12. Reintroduction of Step Annotations: Added step annotations back into the visualization for clarity.
13. Title Color Adjustment: You wanted the titles of the sorting algorithms colored blue.
14. Legend Addition: Asked to add a legend explaining the color coding of the elements.
15. Legend Visibility Issue: Addressed the issue where the video progress bar covered the legend.
16. Conclusion: Expressed satisfaction with the assistance provided.

Python 3 Source: (Run in a Google Colab Jupyter Notebook)

import numpy as np

import matplotlib.pyplot as plt

from matplotlib.animation import FuncAnimation

import matplotlib.patches as mpatches

from IPython.display import HTML

# Initialize data and steps for each sorting algorithm

np.random.seed(0)

data = np.random.randint(0, 100, 40)

steps_qs, markers_qs = [], []

steps_bs, markers_bs = [], []

steps_is, markers_is = [], []

steps_ss, markers_ss = [], []

# Quicksort with detailed tracking

def quicksort(arr, lo, hi, steps, markers):

if lo < hi:

p = partition(arr, lo, hi, steps, markers)

quicksort(arr, lo, p - 1, steps, markers)

quicksort(arr, p + 1, hi, steps, markers)

def partition(arr, lo, hi, steps, markers):

pivot = arr[hi]

i = lo

for j in range(lo, hi):

if arr[j] < pivot:

arr[i], arr[j] = arr[j], arr[i]

i += 1

# Markers: pivot (hi), current item (j), and swap position (i)

markers.append([hi, j, i])

steps.append(arr.copy())

arr[i], arr[hi] = arr[hi], arr[i]

markers.append([hi, i, -1]) # Final swap to place pivot

steps.append(arr.copy())

return i

# Bubblesort with detailed tracking

def bubblesort(arr, steps, markers):

n = len(arr)

for i in range(n):

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]

# Markers: current item (j) and comparison item (j+1)

markers.append([j, j+1])

steps.append(arr.copy())

# Insertionsort with detailed tracking

def insertionsort(arr, steps, markers):

for i in range(1, len(arr)):

key = arr[i]

j = i-1

while j >= 0 and key < arr[j]:

arr[j + 1] = arr[j]

j -= 1

# Markers: current item (i) and shift position (j)

markers.append([i, j])

steps.append(arr.copy())

arr[j + 1] = key

markers.append([i, j+1]) # Placement of key

steps.append(arr.copy())

# Selectionsort with detailed tracking

def selectionsort(arr, steps, markers):

for i in range(len(arr)):

min_idx = i

for j in range(i+1, len(arr)):

if arr[j] < arr[min_idx]:

min_idx = j

arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Markers: minimum item (min_idx) and current position (i)

markers.append([min_idx, i])

steps.append(arr.copy())

# Sort and track steps

quicksort(data.copy(), 0, len(data)-1, steps_qs, markers_qs)

bubblesort(data.copy(), steps_bs, markers_bs)

insertionsort(data.copy(), steps_is, markers_is)

selectionsort(data.copy(), steps_ss, markers_ss)

# Visualization setup

# Define legend handles

legend_handles = [

mpatches.Patch(color='red', label='Unchanged Item'),

mpatches.Patch(color='blue', label='Pivot / Insertion Point'),

mpatches.Patch(color='orange', label='Current Item')

]

# Initialize the figure and axes again if needed

fig, ax = plt.subplots(2, 2, figsize=(8, 8), facecolor='#99CC99')

for axs in ax.flat:

axs.set_facecolor('#99CC99')

# Adjust subplots to make room for the legend below

fig.subplots_adjust(bottom=0.2)

# Animation update function with step annotations

def update(frame):

# Maps for color coding

color_map = {0: 'red', 1: 'blue', 2: 'orange', 3: 'green'}

plots = [steps_qs, steps_bs, steps_is, steps_ss]

titles = ['Quicksort', 'Bubblesort', 'Insertion Sort', 'Selection Sort']

markers = [markers_qs, markers_bs, markers_is, markers_ss]

for axs, plot, title, marker in zip(ax.flat, plots, titles, markers):

axs.clear()

axs.set_title(title, color='blue', fontsize=12)

current_step = plot[min(frame, len(plot)-1)]

if frame < len(marker):

current_marker = marker[frame]

else:

current_marker = [-1] # Default no marker

for i, val in enumerate(current_step):

color = 'red' # Default color

if i in current_marker:

color = color_map[current_marker.index(i)]

axs.bar(i, val, color=color)

# Annotate current step number on each subplot

step_text = f'Step: {min(frame+1, len(plot))}/{len(plot)}'

axs.text(0.35, 0.95, step_text, transform=axs.transAxes, ha='right', va='top', fontsize=12, color='blue', bbox=dict(facecolor='#99CC99', alpha=0.5, edgecolor='none'))

# Adding credit in the last subplot

fig.legend(handles=legend_handles, loc='lower center', bbox_to_anchor=(0.5, 0.1), fancybox=True, shadow=True, ncol=3)

fig.text(1, 0.0, 'Van2024/ChatGPT-4', fontsize=12, color='yellow', horizontalalignment='right', verticalalignment='bottom')

# Creating the animation

ani = FuncAnimation(fig, update, frames=max(len(steps_qs), len(steps_bs), len(steps_is), len(steps_ss)), interval=100, repeat=False)

# Display the animation

HTML(ani.to_html5_video())