- Published on

# Sorting Visualizer Tutorial with React, SVG, ES6 generator function

- Authors
- Name
- Alvin Li

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

## 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 `yield`

ed 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

`function*`

Turning sorting function into sorting 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.

```
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 `yield`

ed by the generator function is representing a certain state of the array. So we can use it to update the state of the component.

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

```
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.

```
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);
}
```

```
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 `yield`

ing 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.

```
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.

```
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.

```
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.

```
// ...
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.

```
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 };
}
```

```
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.

```
// ...
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

```
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!