Portfolio

Algorithm Visualizations

This page features interactive visualizations of some of the most common algorithms in Computer Science and Competitive Programming. From sorting and searching to graph traversal and dynamic programming, you’ll be able to explore how these algorithms work step by step.

Grid Traversals

This visualization shows several graph-search algorithms that traverse a grid and often aim to find the shortest path between nodes. Each square is a node in a graph, and each pair of non-diagonally adjacent squares forms an edge, in this case all edges are unweighted. These algorithms power things like map routing from your current location to a destination.

X

You can move the circle (start node) and cross (end node) to your liking, and click around the grid to place walls. Then just select the algorithm, adjust the speed and let the visualization begin!

Sorting Algorithms

Below is a bar-chart view of an integer array that various sorting algorithms will reorder. Each algorithm has different trade-offs in speed, memory, and data-structure fit. Standard arrays are the usual choice of data structure for most algorithms, though merge sort on a linked list can save auxiliary memory at the cost of cache locality.

Select an algorithm, randomize the order or shift elements around, then press Visualize.

Convex Hull Problem

The Convex Hull problem is a problem in mathematics and more specifically computational geometry, which asks: given a finite set of points in some subset of the Euclidean space, what is the polytope which contains all points that has the smallest n-dimensional volume? This problem comes up frequently in computer graphics and robotics applications, usually the dimension of the Euclidean space is 2 or 3 depending on the use-case. A creative way to visualize what this is in 2 dimensions is to imagine a set of points on the plane and placing a rubber band around the points, the shape which the rubber band will contract to will be the shape of the 2D Convex Hull. There are many algorithms capable of finding the Convex Hull, a very popular one is Quickhull, which is usually used for the 3D version of the problem. The algorithm I am showcasing here is called the Graham Scan.

Graham Scan

The Graham Scan is an algorithm developed to find the Convex Hull of a finite set of points in 2D Euclidean space, the main geometric ideas behind it only work in 2D.

The main steps of the algorithm are:

  1. Select a pivot point, typically the farthest point in a corner direction, in this case it’s the highest point, ties broken by x-coordinate, so top left-most point
  2. Sort the remaining points by polar angle with respect to the pivot.
  3. Sweep through the sorted points with a monotonic stack, whenever the next point makes a right turn (clockwise) with the top two stack points, pop the top of the stack.
  4. After you have swept through the entire list, the points remaining in the stack are the vertices of the convex hull.

This algorithm runs in O(n log n) time due to the initial sort, after that the sweep is linear.

The space complexity is O(n) due to the use of the monotonic stack.