Inspired by Clément Mihailescu's video in building a sorting visualizer, I decided to build one by myself before watching the video. The first idea I could think of is ES6 generator functions. This article meant to be a step-by-step tutorial just like how I was building it at first. I will describe how I formulate the problem, what I tried and what I chose. Let's go!

Table of Contents

Generator functions

For those who don't know what generator functions are, basically they are functions that can be paused and resumed. Generator function itself (function*) is a function that returns a generator object. You can think it as a blueprint for creating a factory, and the generator, aka the factory, will spit out the values that are yielded by the factory.

// Generator function
function* generateNumbers() {
  for (let i = 0; i < 3; i++) {
    yield i
  }
  return 'finished!'
}

// Initialize the generator object
const generator = generateNumbers()
// Get the values one by one
console.log(generator.next()) // { value: 0, done: false }
console.log(generator.next()) // { value: 1, done: false }
console.log(generator.next()) // { value: 2, done: false }
console.log(generator.next()) // { value: "finished!", done: true }
// function has already exited
console.log(generator.next()) // { value: undefined, done: true }

In line 10 above, a generator object generator is initialized, but the function body of generatorNumbers has not been executed yet. generator.next() executes the function until it encounters a yield statement. Then the next .next() call will resume the function and so on. When the function has exited just like any other normal function, the generator object will have a done property set to true.

The value property in the returned object by next() can be a yielded value or a return value of the function. Of course, the return function of a void function is undefined. just like any other javascript functions. It is noteworthy that any subsequent next() call after the function has exited will return { value: undefined, done: true }.

Generator function is a perfect fit for building a sorting visualizer because we need to know what's going on in each step of the sorting algorithm. With generators, we can "freeze the time" until we decide to continue the next step. So how does it actually work?

Implementing

Turning sorting function into sorting `function*`

Let's look at the classic bubble sort algorithm.

function bubbleSort(arr: number[]) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
}

With generator function, we can pause the function by placing a yield statement in the middle of the for loop, right before the if statement. The reason that we dont place it inside the if statement is because we want to know the state of the array no matter a swap is needed or not.

We also return the array at last, even if this is an in-place sorting, as the returned value will appear in the next() call too.

bubble-sort.ts

function* bubbleSort(arr: number[]) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      yield arr;
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

Using with React

One fundamental concept of React is that the "View" should always be a derived value of the "state" and "props". We should always avoid changing the UI directly but instead update the state and reflect the changes in UI. In today's case, the value yielded by the generator function is representing a certain state of the array. So we can use it to update the state of the component.

make-random-array.ts

const makeRandomArray = (length: number) => {
  const arr = [];
  for (let i = 0; i < length; i++) {
    arr.push(Math.round(Math.random() * 1000));
  }
  return arr;
};

App.tsx

import { bubbleSort } from "./bubble-sort";
import { makeRandomArray } from "./make-random-array";
import { useState } from "react";

const generator = bubbleSort(makeRandomArray(10));

export default function App() {
  const [sortingState, setSortingState] = useState(() => generator.next());

  const sort = () => {
    if (!sortingState.done) {
      setSortingState(generator.next());
    }
  };

  return (
    <div>
      <button onClick={sort}>Next step</button>
      <pre>{JSON.stringify(sortingState, null, 2)}</pre>
    </div>
  );
}

Result 1 - Demo using generator

Do you know why you shouldn't write useState(generator.next())?
Answer
Although the initial state of useState() will not change on subsequent renders, generator.next() will still be called every time and the sorting state will jump forward by one frame unexpectedly. This might also cause sortState.value to be undefined and costs you hours to debug. Be careful!

Visualizing

Let's draw some vertical bars filling the screen to represent the array values. We also need some spaces for the controls toolbar at the top of the screen.

I chose to use SVG instead of normal divs because it is easier to position the bars. We can simply place the bars at certain % position and that's it!

The SVG coordinates starts from top-left but I want the bars to stick to bottom, so I inverted the axis by applying transform: scaleY(-1); to the svg container.

styles.css

html,
body {
  margin: 0;
  padding: 0;
}
.body-container {
  display: flex;
  flex-direction: column;
  height: 100vh;
  max-height: 100vh;
}
.toolbar {
  display: flex;
  justify-content: center;
  align-items: center;
}
.svg-content {
  flex-grow: 1;
  width: 100%;
  transform: scaleY(-1);
}

App.tsx

import "./styles.css";
import { bubbleSort } from "./bubble-sort";
import { makeRandomArray } from "./make-random-array";
import { useState } from "react";

const generator = bubbleSort(makeRandomArray(10));

export default function App() {
  const [sortingState, setSortingState] = useState(() => generator.next());

  const sort = () => {
    if (!sortingState.done) {
      setSortingState(generator.next());
    }
  };

  const array = sortingState.value;

  return (
    <div className="body-container">
      <div className="toolbar">
        <button onClick={sort}>Sort</button>
      </div>
      <svg
        className="svg-content"
        preserveAspectRatio="none"
        height="100%"
        width="100%"
      >
        <rect x={0} y={0} width="100%" height="100%" fill="black" />
        {array.map((value, index) => {
          const height = `${(value / 1000) * 100}%`;
          const width = `${100 / array.length}%`;
          const x = `${(100 * index) / array.length}%`;
          return (
            <rect
              stroke="black"
              strokeWidth={1}
              key={index}
              fill="white"
              x={x}
              y={0}
              height={height}
              width={width}
            />
          );
        })}
      </svg>
    </div>
  );
}

Result 2 - Demo using SVG

Now we have successfully showed the position of each bar in a certain moment. Let's implement the details that make a sorting visualizer attractive!

Adding more visualizations

Determining the information we need

Before writing any code, we need to know what information we need to visualize the sorting process. The most basic function of a sorting visualizer would be to show which bars we are comparing, whether it needs sorting and how their positions change after being sorted. With generator functions, this is as simple as yielding multiple times at suitable positions.

Other than yielding the array, we also need the information of the stuff we are dealing at. There are various ways to achieve this. By yielding:

{ array: number[], comparingLeftIndex: number; comparingRightIndex: number }
This leaves the color mapping to the react component. Not a bad idea but the type of the yielded and returned value of the generator function will have to include a lot of different keys to cater the need of different sorting algorithms. For example, Insertion sort might need to indicate a pivot index. but we should not care about this in a shared interface.
{ array: number[], barStates: { 3: 'compareLeft', 4: 'compareRight', 5: 'pivot'} } The interface has become a lot simpler but the value of each barState still has to be a large union of wordings from different sorting algorithms. Not scalable too.
{ array: number[], colors: { 3: 'yellow', 4: 'green' } } This method leaves the color mapping encapsulated with the sorting algorithm itself, and the react component can easily consume the colors in drawing the bars. We can freely choose different colors for different bar index without worrying the naming problem.

Writing an interface for sorting generator function

We will go for the third option above. Let's take a close look at the signature of es6 generator function.

We can safely ignore the generic TNext for now.

lib.es2015.generator.d.ts

interface IteratorYieldResult<TYield> {
    done?: false;
    value: TYield;
}

interface IteratorReturnResult<TReturn> {
    done: true;
    value: TReturn;
}

type IteratorResult<T, TReturn = any> = IteratorYieldResult<T> | IteratorReturnResult<TReturn>;

interface Generator<T = unknown, TReturn = any, TNext = unknown> extends Iterator<T, TReturn, TNext> {
    next(...args: [] | [TNext]): IteratorResult<T, TReturn>;
    return(value: TReturn): IteratorResult<T, TReturn>;
    throw(e: any): IteratorResult<T, TReturn>;
    [Symbol.iterator](): Generator<T, TReturn, TNext>;
}

We can see that the first two generatic type corresponds to the yield and return result respectively. To keep things consistent, we should use the same type for both to avoid unnecessary type checkings.

types.ts

export type StepState = {
  result: number[];
  colors?: Record<number, string>;
};

export type SortingGenerator = Generator<StepState, StepState>

In the bubble sort function, let's render both bars as yellow if their position is correct. Otherwise, show different colors if they are originally out of other then also show the result after swapping.

bubble-sort.ts

import { SortingGenerator } from "./types";

export function* bubbleSort(arr: number[]): SortingGenerator {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Out of position, yield twice
        yield {
          result: arr,
          colors: { [j]: "yellow", [j + 1]: "green" },
        };
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        yield {
          result: arr,
          colors: { [j]: "green", [j + 1]: "yellow" },
        };
      } else {
        // In correct order, yield once
        yield {
          result: arr,
          colors: { [j]: "yellow", [j + 1]: "yellow" },
        };
      }
    }
  }
  return { result: arr };
}

Consuming the colors

With the object of colors indexed by bar index, we can use colors?.[index] to get the special color for that bar, and render white if we did not assign a special color for it.

App.tsx

// ...
export default function App() {
  // ...
  const { result, colors } = sortingState.value;

  return (
    <div className="body-container">
      <div className="toolbar">
        <button onClick={sort}>Sort</button>
      </div>
      <svg className="svg-content" height="100%" width="100%">
        <rect x={0} y={0} width="100%" height="100%" fill="black" />
        {result.map((value, index) => {
          const height = `${(value / 1000) * 100}%`;
          const width = `${100 / result.length}%`;
          const x = `${(100 * index) / result.length}%`;
          return (
            <rect
              stroke="black"
              strokeWidth={1}
              key={index}
              fill={colors?.[index] ?? "white"}
              x={x}
              y={0}
              height={height}
              width={width}
            />
          );
        })}
      </svg>
    </div>
  );
}

Result 3 - Coloring SVGs

🎉 Now we have a lively animation to show the process of comparision and swapping! Let's move on to handle other kinds of sorting algorithms.

Algorithms with recursion

Figuring out what should be yielded

One of the most popular sorting algorithms is merge sort. It is a divide and conquer algorithm and it can be implemented with recursion. We don't need to worry about because its maximum recursion depth is $\log_2(n)$ . For demo pursepose, we will use a simple, non-in-place version of merge sort. The In-Place merge sort generator function will also be include in the final product, for those who are interested.

A normal merge sort function looks like this

export function mergeSort(arr: number[], i: number = 0, j: number = arr.length - 1) {
  if (j <= i) return
  const middle = Math.floor((j - i) / 2) + i
  mergeSort(arr, i, middle)
  mergeSort(arr, middle + 1, j)
  merge(arr, i, middle, j)
}

export function merge(arr: number[], i: number, middle: number, j: number) {
  let left = i
  let right = middle + 1
  const sorted: number[] = []
  while (left <= middle && right <= j) {
    if (arr[left] <= arr[right]) {
      sorted.push(arr[left])
      left++
    } else {
      sorted.push(arr[right])
      right++
    }
  }
  while (left <= middle) {
    sorted.push(arr[left])
    left++
  }
  while (right <= j) {
    sorted.push(arr[right])
    right++
  }
  for (let k = 0; k < sorted.length; k++) {
    arr[i + k] = sorted[k]
  }
}

The process of merge sort includes

Dividing the array into two halves. We need to indicate the boundaries and the middle point in the diagram.
Merging left and right halves by taking the smaller element from the two halves and pushing it into the sorted array. We need to show which element we are pushing.
Writing the sorted array back to the original array. We also need to show the steps of writing elements.

This results in the following yields

yield the boundaries and middle value of the current scope immediately after mergeSort() is called
When the mergeSort() is called with the left half of the array, yield the corresponding boundaries of the smaller half
Repear step 2 for the right half
When merge() is called, yield the current element being pushed into the array
After completing the sorted array, yield the current element being written back to the original array

Recursive Generator functions

As both functions mergeSort() and merge() should be generator functions and mergeSort() calls merge() during its lifetime, we need to use the yield* operator to "delegate" the yield to another generator function until the function is done.

You will need to set "downlevelIteration": true in tsconfig.json to use this feature.

TL;DR: change all function to function*and putyield* before every function call on generator functions.

Notice that I write a helper function function* push() inside merge() to avoid code duplication. Remember: generate functions are just functions. The way to abstract generator functions is same as TL;DR above.

mergeSort()

export function* mergeSort(
  arr: number[],
  i = 0,
  j = arr.length - 1
): SortingGenerator {
  const middle = Math.floor((j - i) / 2) + i;

  // Step 1,2,3
  yield {
    result: arr,
    colors: {
      [i]: "yellow",
      [middle]: "blue",
      [j]: "green",
    },
  };
  if (j <= i) return { result: arr };

  yield* mergeSort(arr, i, middle);
  yield* mergeSort(arr, middle + 1, j);
  yield* merge(arr, i, middle, j);

  return { result: arr };
}

merge()

export function* merge(
  arr: number[],
  i: number,
  middle: number,
  j: number
): SortingGenerator {
  let left = i;
  let right = middle + 1;
  const sorted: number[] = [];

  // Helper function to simplify repeated yields
  function* push(index: number) {
    // Step 4
    yield {
      result: arr,
      colors: {
        [middle]: "blue",
        [index]: "red",
      },
    };
    sorted.push(arr[index]);
  }

  while (left <= middle && right <= j) {
    if (arr[left] <= arr[right]) {
      yield* push(left);
      left++;
    } else {
      yield* push(right);
      right++;
    }
  }
  while (left <= middle) {
    yield* push(left);
    left++;
  }
  while (right <= j) {
    yield* push(right);
    right++;
  }

  for (let k = 0; k < sorted.length; k++) {
    // Step 5
    yield {
      result: arr,
      colors: {
        [i + k]: "yellow",
      },
    };
    arr[i + k] = sorted[k];
  }
  return { result: arr };
}

Now put this use this function in our visualizer to see the results.

App.tsx

// ...
import { mergeSort } from "./merge-sort";

const generator = mergeSort(makeRandomArray(10));
// ...

Result 4 - Merge sort

Sidenote: <StrictMode> was enabled in codesandbox and it will render our component twice (not a bug). We will just remove strict mode for now and the problem of double rendering will be solved later on.

Resetting and generating a new array

When a generator is already done, subsequent call on the generator will return { value: undefined, done: true }. If we want to start a sort, we will need a new generator. To tackle this, we can store the generator in state. This will also solve the StrictMode problem mentioned above

App.tsx

export default function App() {
  const [generator, setGenerator] = useState(mergeSort(makeRandomArray(10)));
  const [sortingState, setSortingState] = useState(() => generator.next());

  const sort = () => {
    if (!sortingState.done) {
      setSortingState(generator.next());
    }
  };

  const reset = () => {
    const newGenerator = mergeSort(makeRandomArray(10));
    setGenerator(newGenerator);
    setSortingState(newGenerator.next());
  };

  return //...
}

Result 5 - Resetting Array

Misc features

The main features has already been implemented 🎉

The rest of this article will also include some other features that I have implemented for fun, and for users' satisfaction. We will not go into too much detail. The full implementation is available in the GitHub repository.

Keep reading!

Algorithm selector

This is a must have feature to let user choose the algorithm to visualize. We can use a map to store the generators and their names.

export const algorithms = {
  bubbleSort,
  insertionSort,
  mergeSort,
  quickSort,
  inPlaceMergeSort,
} as const
export const algorithmNames = {
  bubbleSort: 'Bubble Sort',
  insertionSort: 'Insertion Sort',
  mergeSort: 'Merge Sort',
  quickSort: 'Quick Sort',
  inPlaceMergeSort: 'In-Place Merge Sort',
} as const
export type AlgorithmKey = keyof typeof algorithmNames
export const algorithmKeys = Object.keys(algorithmNames) as AlgorithmKey[]

// In component
const [algorithmKey, setAlgorithmKey] = useState<AlgorithmKey>('mergeSort')
const selectedAlgorithm = algorithms[algorithmKey]

const [sortGenerator, setSortGenerator] = useState(selectedAlgorithm(randomArray(ARRAY_LEN)))
const [sortState, setSortState] = useState(() => sortGenerator.next())
const reset = useCallback(() => {
  const newGenerator = selectedAlgorithm(randomArray(ARRAY_LEN))
  const next = newGenerator.next()
  setSortGenerator(newGenerator)
  setSortState(next)
}, [selectedAlgorithm])

Abstracting the logic into a custom hook with callbacks

For DX and maintainability and keeping the main file clean. We can abstract the logic into a custom hook.

const { algorithmKey, setAlgorithmKey, reset, nextStep, sortState } = useSorting({
  onReset: () => {},
  onAlgorithmChange: (algorithmKey) => {},
})

Autoplay

We all know that it feels good to watch the bars being swapped and sorted. I implemented a slow and fast play mode to let user choose the speed of the animation.

This can be done by using useRafLoop (abbr for useRequestAnimationFrameLoop) from the react-use package. It works identically to useEffect + requestAnimationFrame but hides some details in calling the loop and provides a more convenient API to start / stop the loop.

const [mode, setMode] = useState<Mode>(Mode.Pause)
const { algorithmKey, setAlgorithmKey, reset, nextStep, sortState } = useSorting({
  onReset: () => {
    setMode(Mode.Pause)
  },
  onAlgorithmChange: () => {
    setMode(Mode.Pause)
  },
})

const lastCalled = useRef(0)
const delta = useRef(50)

const [loopStop, loopStart] = useRafLoop((time) => {
  if (time - lastCalled.current > delta.current) {
    nextStep()
    lastCalled.current = time
  }
  if (sortState?.done) {
    setMode(Mode.Pause)
  }
})

useEffect(() => {
  if (mode === Mode.Pause) {
    loopStop()
    return
  }
  loopStart()
  if (mode === Mode.Play) {
    delta.current = 60
  } else {
    delta.current = 9
  }
}, [loopStop, loopStart, mode])

Final words

This is my first attempt to summarize my coding experience with an article. If you like this and would like to see more of this, please share and comment!

Generator functions

Implementing

Turning sorting function into sorting function*

Using with React

Result 1 - Demo using generator

Visualizing

Result 2 - Demo using SVG

Adding more visualizations

Determining the information we need

Writing an interface for sorting generator function

Consuming the colors

Result 3 - Coloring SVGs

Algorithms with recursion

Figuring out what should be yielded

Recursive Generator functions

Result 4 - Merge sort

Resetting and generating a new array

Result 5 - Resetting Array

Misc features

Algorithm selector

Abstracting the logic into a custom hook with callbacks

Autoplay

Final words

Turning sorting function into sorting `function*`