Table of Contents

1. Introduction
2. The first approach
3. Understanding JS Generators
4. Applying Generators to the Algorithm Visualizer

Introduction

Thinking about projects to work on to learn a bit more and try something different, I came up with the idea of creating the typical sorting algorithm visualizer for algorithms like Bubble Sort, Quick Sort, Merge Sort, etc.

For this article, I’ll focus on Bubble Sort, although the same approach can be applied to any algorithm or piece of code that we want to visualize.

The first approach

The idea was as follows: on one hand, we had the Bubble Sort algorithm:

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; ++i) {
    let swapped = false;
    for (let j = 0; j < arr.length - i - 1; ++j) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}

And on the other hand, a function that will execute the algorithm and update the visualization as the algorithm runs. To achieve this, the first thing that came to mind was to add this.refresh() to the point where the elements are swapped in the algorithms.

This way, every time an element is swapped, the visualization would be updated. An example might be the following:

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; ++i) {
    let swapped = false;
    for (let j = 0; j < arr.length - i - 1; ++j) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        this.refresh(arr[j], arr[j + 1]); // <- Here the visualization is updated
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}
 
class BasicController {
  refresh(a, b) {
    console.log(`Swapping ${a} and ${b}`);
  }
 
  play() {
    const arr = [2, 5, 1, 3];
    console.log("Initial array:", arr);
    const sortedArr = bubbleSort.call(this, arr);
    console.log("Sorted array:", sortedArr);
  }
}
 
const controller = new BasicController();
controller.play();

If we run the code, we will get the following output:

Initial array: [ 2, 5, 1, 3 ]
Swapping 1 and 5
Swapping 3 and 5
Swapping 1 and 2
Sorted array: [ 1, 2, 3, 5 ]

In this example, the refresh has been implemented to log element swaps to the console, but in a real visualizer, you could update the visualization in any desired way.

The idea isn’t entirely bad, but it has several issues:

1. For the visualization, it would be ideal for it to be asynchronous, meaning it should be able to pause at any moment and resume later, allowing you to see the state of the array at each iteration.
2. If the algorithm runs and doesn’t find the this.refresh() function, it will throw an error.

Of course, we could solve this just by adding each time the array is swapped to a list and then executing the visualization at the end, but this wouldn’t be the most efficient way to do it and not the most elegant either. This is where JavaScript generators come into play.

Understanding JS Generators

JavaScript generators are special functions that differ primarily from normal functions in that they execute step by step. That is, when a generator is called, it does not run to completion. Instead, it executes up to a certain point or breakpoint, returns a value, and pauses execution with the option to resume later.

On one hand, we have the generator function function*, where the asterisk * indicates that it is a generator function. On the other hand, we have the yield keyword, which is used to return a value and pause the execution of the generator function.

An example of a Fibonacci sequence function without generators would be:

function fibonacci(n) {
  let a = 0,
    b = 1;
  for (let i = 0; i < n; ++i) {
    let temp = a;
    a = b;
    b = temp + b;
  }
  return a;
}

And the same function using generators would be:

function* fibonacci(n) {
  let a = 0,
    b = 1;
  for (let i = 0; i < n; ++i) {
    let temp = a;
    a = b;
    b = temp + b;
    yield a;
  }
}

An example of how to use the generator would be:

function* fibonacci(n) {
  let a = 0,
    b = 1;
  for (let i = 0; i < n; ++i) {
    let temp = a;
    a = b;
    b = temp + b;
    yield a;
  }
}
 
// We initialize the generator with n = 5
const gen = fibonacci(5);
 
// Iterate over the generator and print the values of the Fibonacci sequence
let result = gen.next();
while (!result.done) {
  console.log(result.value);
  result = gen.next();
}

In this case, gen is the generator created from the fibonacci function. To obtain the values of the Fibonacci sequence up to n, you use the next() method of the generator, which will return an object with two properties: value and done.

First, value will be the value returned by yield, and done will be a boolean indicating whether the generator has finished or not.

If we run it, we will get the following output:

1 1 2 3 5

Applying Generators to the Algorithm Visualizer

Now that we know how generators work, let’s apply them to the algorithm visualizer. To do this, we will modify the Bubble Sort algorithm to be a generator and execute it step by step.

function* bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; ++i) {
    let swapped = false;
    for (let j = 0; j < arr.length - i - 1; ++j) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        yield arr.slice(); // <- Here the state of the array is returned
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}

In this case, the bubbleSort generator will return the current state of the array at each iteration. To get the current state of the array, yield arr.slice() is used, which returns a copy of the array at that moment.

We will modify the controller to execute the generator step by step:

class BasicController {
  constructor() {
    this.arr = [2, 5, 1, 3];
    this.gen = bubbleSort(this.arr); // We initialize the generator
    console.log("Initial array:", this.arr);
  }
 
  refresh(a, b) {
    console.log(`Swapping ${a} and ${b}`);
  }
 
  step() {
    const result = this.gen.next();
    if (!result.done) {
      console.log("Current array:", result.value);
    } else {
      console.log("Sorted array:", result.value);
    }
  }
}
const controller = new BasicController();
controller.step(); // Executes the first step
controller.step(); // Executes the second step
controller.step(); // ... and so on

If we run the code, we will get the following output:

Initial array: [ 2, 5, 1, 3 ]
Current array: [ 2, 1, 5, 3 ]
Current array: [ 2, 1, 3, 5 ]
Current array: [ 1, 2, 3, 5 ]

In this way, we could execute the algorithm step by step and visualize the state of the array at each iteration, with the ability to pause at any moment to view the current state. Here are two quick visualization examples created in just a few minutes using the same strategy of using generators:

For a more realistic and comprehensive example, you can check out the sorting algorithm visualizer I created at this link, with the GitHub repository available here.