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())

Blazing Fast TSP: Comparing Brute Force and 2-Opt Algorithms

I recently encountered a solicitation on LinkedIn that said, "You have been selected to explain the Traveling Salesman Problem". (TSP). The solicitation turned out to be a way of getting multiple computer science people to solve the same problem, which would then be Darwinized and used by LinkedIn for further promotion. I provided a complete solution, but they would not accept a link, presumably because it takes the user off-site, which is anathema to social media profits. Beware the Machine.

Nonetheless, I thought this would be a good opportunity to demonstrate automatic code generation with a Large Language Model (LLM). So I set about with the following request:

Dear ChatGPT - I appreciate you so much! You have been an honest and faithful helper in coding up demonstrations of various principles in computer science, numerical analysis, computer graphics, and anything I'm interested in. Tonight, I need your help coding up a simple but beautiful demonstration of approaches to solving the Traveling Salesman Problem (TSP). As you know, this famous problem in computer science and operations research is well known for its pathological growth characteristics in time complexity. Nonetheless, we have to solve such problems, even if we cannot be guaranteed the optimal solution. I want you to build a Python demonstration compatible with Google Colab that uses matplotlib to generate approaches to solving TSP. It should run as an interactive demo that I can record off my screen.

While in previous blogs this approach yielded a straightforward generation processes, the more typical route to a working demo with satisfactory appearance is MUCH more circuitous.  One shot solutions are the exception to the rule, this effort required 29 iterations in ChatGPT 3.5 and 10 more in ChatGPT 4! Pressing on:
In the world of computer science and operations research, few problems are as iconic and challenging as the Traveling Salesman Problem (TSP). The TSP asks a simple question with profound implications: given a list of cities and the distances between them, what is the shortest possible route that visits each city exactly once and returns to the original city? Despite its seemingly straightforward nature, the TSP is notorious for its time complexity, which is exponential in the number of cities, making it a fascinating subject for exploration. This kind of complexity is informally called "hockey-stick growth". As each additional city case is processed in a brute force approach, all previous cases are relegated to be of low complexity in comparison.

In this blog post, we embark on a journey through the world of TSP-solving algorithms, focusing on two primary approaches: brute force and 2-opt. We'll delve into the inner workings of these algorithms, explore their strengths and weaknesses, and compare their performance in solving increasingly complex instances of the TSP.

Brute Force: The Traditional Approach

We kick off our exploration with the brute force algorithm, the most straightforward method for solving the TSP. Brute force systematically evaluates every possible permutation of city visitation order, calculating the total distance traveled for each permutation and selecting the shortest route. While conceptually simple, brute force quickly becomes impractical for large numbers of cities due to its exponential time complexity.

import numpy as np

import matplotlib.pyplot as plt

import time

from itertools import permutations

# Function to solve TSP using brute force

def brute_force_tsp(points):

min_dist = float('inf')

max_dist = 0

best_path = None

all_paths = []

start_time = time.time()

for perm in permutations(points):

dist = sum(np.linalg.norm(np.diff(perm, axis=0), axis=1))

all_paths.append(np.array(perm)) # Convert the tuple to a NumPy array

if dist < min_dist:

min_dist = dist

best_path = perm

if dist > max_dist:

max_dist = dist

end_time = time.time()

return best_path, min_dist, max_dist, all_paths, end_time - start_time

2-Opt: A Smarter Solution

Next, we introduce the 2-opt algorithm, a more sophisticated approach that seeks to improve upon the limitations of brute force. 2-opt operates by iteratively swapping pairs of edges in the current solution, aiming to reduce the total distance traveled. Unlike brute force, 2-opt exhibits polynomial time complexity, making it more scalable for larger problem instances. However, 2-opt does not guarantee optimal solutions and may occasionally converge to suboptimal routes.

# Function to solve TSP using 2-opt heuristic

def tsp_2opt(points):

n = len(points)

path = np.arange(n)

improvement = True

best_dist = sum(np.linalg.norm(np.diff(points, axis=0), axis=1))

while improvement:

improvement = False

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

for j in range(i + 1, n):

new_path = path.copy()

new_path[i:j] = path[j - 1:i - 1:-1]

new_dist = sum(np.linalg.norm(np.diff(points[new_path], axis=0), axis=1))

if new_dist < best_dist:

best_dist = new_dist

path = new_path

improvement = True

break

if improvement:

break

return path, best_dist, improvement

Comparative Analysis: Brute Force vs. 2-Opt

With both algorithms in hand, we conduct a comparative analysis to evaluate their performance across various TSP instances. We examine factors such as execution time, solution quality, and scalability, shedding light on the trade-offs between computational efficiency and solution optimality. 

Conclusion: Navigating the TSP Landscape

In conclusion, our exploration of the Traveling Salesman Problem has provided valuable insights into the world of combinatorial optimization. While brute force offers a straightforward and reliable method for finding optimal solutions, its computational demands prove prohibitive for larger problem sizes. In contrast, 2-opt presents a more scalable alternative, leveraging heuristic techniques to efficiently explore solution space. By understanding the nuances of each approach, practitioners can navigate the TSP landscape with confidence, selecting the most appropriate algorithm for their specific requirements.

Join us on this journey as we unravel the complexities of the Traveling Salesman Problem, uncovering the algorithms and strategies that drive computational optimization in the digital age.

The remaining source code is below, it can be run in Google Colab for free!
But beware, it slows down significantly for more than about 8 cities!

# Test cases (number of cities)

test_cases = range(2, 8)

brute_force_runtimes = []

brute_force_shortest_distances = []

brute_force_longest_distances = []

num_paths = []

# Combined demonstration

plt.figure(figsize=(14, 12), facecolor='#99CC99')

for idx, num_points in enumerate(test_cases, start=1):

points = np.random.rand(num_points, 2)

# Solve TSP using brute force approach

best_path_brute_force, min_dist_brute_force, max_dist_brute_force, all_paths_brute_force, brute_force_runtime = brute_force_tsp(points)

brute_force_runtimes.append(brute_force_runtime)

brute_force_shortest_distances.append(min_dist_brute_force)

brute_force_longest_distances.append(max_dist_brute_force)

num_paths.append(len(all_paths_brute_force))

# Plot all attempted paths for brute force

plt.subplot(4, len(test_cases), idx)

for path in all_paths_brute_force:

path_list = path.tolist()

plt.plot(np.append([point[0] for point in path_list], path_list[0][0]),

np.append([point[1] for point in path_list], path_list[0][1]),

color='black', linestyle='-', linewidth=0.5, alpha=0.5)

plt.scatter(points[:,0], points[:,1], color='red', zorder=2)

plt.title(f'Brute Force\nCities: {num_points}\nShortest: {min_dist_brute_force:.2f}\nLongest: {max_dist_brute_force:.2f}', backgroundcolor='#99CC99')

# Solve TSP using 2-opt approach

best_path_2opt, min_dist_2opt, _ = tsp_2opt(points)

# Plot 2-opt path

plt.subplot(4, len(test_cases), len(test_cases) + idx)

plt.plot(np.append(points[best_path_2opt, 0], points[best_path_2opt[0], 0]),

np.append(points[best_path_2opt, 1], points[best_path_2opt[0], 1]),

color='red', linestyle='-', linewidth=1, zorder=3)

plt.scatter(points[:,0], points[:,1], color='red', zorder=2)

plt.title(f'2-Opt\nDistance: {min_dist_2opt:.2f}', backgroundcolor='#99CC99')

plt.tight_layout()

plt.show()

plt.figure(figsize=(7,6), facecolor='#99CC99')

# Plot number of paths as a function of the number of cities

plt.subplot(2, 1, 1)

plt.plot(test_cases, num_paths, marker='o', color='green')

plt.xlabel('Number of Cities')

plt.ylabel('Number of Paths')

plt.title('Number of Paths vs. Number of Cities', backgroundcolor='#99CC99')

# Plot summary graphs

plt.subplot(2, 1, 2)

plt.plot(test_cases, brute_force_runtimes, label='Brute Force', marker='o')

plt.xlabel('Number of Cities')

plt.ylabel('Time (seconds)')

plt.title('Execution Time Comparison', backgroundcolor='#99CC99')

plt.legend()

plt.tight_layout()

plt.show()