Gal Elmalah

Posted on Nov 2, 2020 • Edited on Dec 17, 2022 • Originally published at galelmalah.com

Visualizing Bubble Sort in 5 Minutes Using HTML5 Canvas API

#javascript #html #webdev #algorithms

For most developers, bubble sort is one of the first algorithms we learn. Therefore, visualizing it can be highly satisfying and feels a bit like meeting an old friend after a long time.

This article will take you through visualizing the bubble sort algorithm using HTML5 canvas API.

If you would like to jump straight to the results and have a look at the code, here is a codepen.

In the meantime, below is a little sneak peek of what we are going to accomplish here.

If you want to follow along, run the following command to get the initial boilerplate code generated into your working directory.

npx scaffolder-cli i --from-github https://github.com/galElmalah/scaffolder-canvas-template.git --template canvas && cd visualizing-bubble-sort

This will leverage Scaffolder to create the initial setup.

Or create a basic index.html file and script.js.

Now lets jump right ahead and start coding

All of the javascript code is written in script.js.

The first thing we will need is an unsorted array to sort.
Let's write a helper function for creating shuffled arrays.

	const shuffledArrayInRange = (bottom = 1, top = 30) => {
	const arr = [];
	for (let i = bottom; i < top; i++) arr.push(i);
	return arr.sort((a, b) => (Math.random() > 0.5 ? 1 : -1));
	};

view raw script.js hosted with ❤ by GitHub

Cool. Now, we will write a simple implementation of the bubble sort algorithm.

	const bubbleSort = (array, onAction) => {
	for (let i = 0; i < array.length; i++) {
	for (let j = 0; j < array.length; j++) {
	if (array[j] > array[j + 1]) {
	let tmp = array[j];
	array[j] = array[j + 1];
	array[j + 1] = tmp;
	}
	}
	}
	return array;
	};

view raw script.js hosted with ❤ by GitHub

Next, we'll get our canvas and create a context.

	const canvas = document.querySelector("canvas");
	canvas.height = window.innerHeight;
	canvas.width = window.innerWidth;
	const ctx = canvas.getContext("2d");

view raw script.js hosted with ❤ by GitHub

So we got all the basics covered, and now it's up to us to decide how to visualize the array.
The most straightforward way is to just draw a rectangle corresponding to each array element, and set the height according to that element value (the higher the value the higher the rectangle will be).

Here is a representation of our custom rectangle.


	function ArrayMember(x, y, width, height, color = "gray") {
	this.x = x;
	this.y = y;
	this.width = width;
	this.height = height;
	this.color = color;

	this.draw = () => {
	ctx.fillStyle = this.color;
	ctx.fillRect(this.x, this.y, this.width, this.height);
	};

	this.resetColor = () => this.setColor("gray");

	this.setColor = (color) => {
	if (!this.isSorted()) {
	this.color = color;
	}
	};

	this.isSorted = () => this.color === "green";

	this.sorted = () => (this.color = "green");

	this.setValue = (v, color) => {
	if (!this.isSorted()) {
	this.height = v;
	this.setColor(color);
	}
	};
	this.getValue = (v) => this.height;
	}

view raw script.js hosted with ❤ by GitHub

Let's test that everything is working as expected, by drawing our shuffled array.

	const randomArray = shuffledArrayInRange();
	const arrayMembers = randomArray.map((v, i) => {
	return new ArrayMember(10 * i + i, 0, 10, v * 5);
	});

	const drawAll = () => arrayMembers.forEach((m) => m.draw());
	drawAll()

view raw script.js hosted with ❤ by GitHub

Multiply each height param by 5 to get a nice scale, so each pixel will equal 5 pixels.

We can make the height and width of the rectangle dynamic, by making it span the full height and width of the screen.
Try doing this yourself.
Here is a working example for the lazy ones (notice the calcMembersHeightScale and calcMembersWidth functions).

If all goes well, you should see something similar to the following in your browser.

Now, let's go back to our sorting function. What are the actions and states we care about? compare, swap, and sort.
Let's add a custom action dictionary.

	const ACTIONS = {
	SORT: "SORT",
	COMPARE: "COMPARE",
	SWAP: "SWAP",
	};

view raw script.js hosted with ❤ by GitHub

Change our bubble sort function to accept an onAction callback, and call it when an action is made in our bubble sort with the appropriate action.

	const bubbleSort = (array, onAction) => {
	for (let i = 0; i < array.length; i++) {
	for (let j = 0; j < array.length; j++) {
	onAction({ type: ACTIONS.COMPARE, data: [j, j + 1] });
	if (array[j] > array[j + 1]) {
	let tmp = array[j];
	array[j] = array[j + 1];
	array[j + 1] = tmp;
	onAction({ type: ACTIONS.SWAP, data: [j, j + 1] });
	}
	}
	onAction({ type: ACTIONS.SORT, data: array.length - i - 1 });
	}
	return array;
	};

view raw script.js hosted with ❤ by GitHub

We are almost done so hang in there!

What should we do in each action?
Give the members a different color based on the action, and "move" them if necessary - which will just be swapping their values.
Now let's create an action map, according to our known actions.

	const ACTIONS = {
	SORT: "SORT",
	COMPARE: "COMPARE",
	SWAP: "SWAP",
	};

	// ---- what to do on each action ----

	const actionsMap = {
	[ACTIONS.SORT]: (action, members) => members[action.data].sorted(),
	[ACTIONS.SWAP]: (action, members) => {
	const [i, j] = action.data;
	let tmp = members[i].getValue();
	members[i].setValue(members[j].getValue(), "red");
	members[j].setValue(tmp, "yellow");
	},
	[ACTIONS.COMPARE]: (action, members) => {
	const [i, j] = action.data;
	members[i].setColor("blue");
	members[j].setColor("blue");
	},
	};

view raw script.js hosted with ❤ by GitHub

We seem to have all of the parts needed in order to visualize this nifty little thing!
Let's give it a try.

	bubbleSort(randomArray, (action) => {
	actionsMap[action.type](action, arrayMembers);
	ctx.clearRect(0, 0, innerWidth, innerHeight);
	drawAll();
	});

view raw lets_try_it.js hosted with ❤ by GitHub

I'll be damned! it seems like we got only the fully sorted state.
How can we solve this? we need to time our painting somehow.
Let's add two variables, speed which will determine how much time will pass between each step, and ticks to count each call to our onAction callback.

	let ticks = 0;
	const speed = 50;

	bubbleSort(randomArray, (action) => {
	ticks++;
	setTimeout(() => {
	actionsMap[action.type](action, arrayMembers);
	ctx.clearRect(0, 0, innerWidth, innerHeight);
	drawAll(arrayMembers);
	arrayMembers.forEach((m) => m.resetColor());
	}, ticks * speed);
	});

view raw script.js hosted with ❤ by GitHub

A couple of things you should notice in the above example:

Clearing the canvas on each iteration.
Resetting the color property for all of our rectangles on each iteration.

Now putting it all together, we should end up with something like this.

	const canvas = document.querySelector("canvas");
	canvas.height = window.innerHeight;
	canvas.width = window.innerWidth;
	const ctx = canvas.getContext("2d");
	const ACTIONS = {
	SORT: "SORT",
	COMPARE: "COMPARE",
	SWAP: "SWAP",
	};

	const actionsMap = {
	[ACTIONS.SORT]: (action, members) => members[action.data].sorted(),
	[ACTIONS.SWAP]: (action, members) => {
	const [i, j] = action.data;
	let tmp = members[i].getValue();
	members[i].setValue(members[j].getValue(), "red");
	members[j].setValue(tmp, "yellow");
	},
	[ACTIONS.COMPARE]: (action, members) => {
	const [i, j] = action.data;
	members[i].setColor("blue");
	members[j].setColor("blue");
	},
	};

	const shuffledArrayInRange = (bottom = 1, top = 30) => {
	const arr = [];
	for (let i = bottom; i < top; i++) arr.push(i);
	return arr.sort((a, b) => (Math.random() > 0.5 ? 1 : -1));
	};
	const bubbleSort = (array, onAction) => {
	for (let i = 0; i < array.length; i++) {
	for (let j = 0; j < array.length; j++) {
	onAction({ type: ACTIONS.COMPARE, data: [j, j + 1] });
	if (array[j] > array[j + 1]) {
	let tmp = array[j];
	array[j] = array[j + 1];
	array[j + 1] = tmp;
	onAction({ type: ACTIONS.SWAP, data: [j, j + 1] });
	}
	}
	onAction({ type: ACTIONS.SORT, data: array.length - i - 1 });
	}
	return array;
	};

	function ArrayMember(x, y, width, height, color = "gray") {
	this.x = x;
	this.y = y;
	this.width = width;
	this.height = height;
	this.color = color;

	this.draw = () => {
	ctx.fillStyle = this.color;
	ctx.fillRect(this.x, this.y, this.width, this.height);
	};

	this.resetColor = () => this.setColor("gray");

	this.setColor = (color) => {
	if (!this.isSorted()) {
	this.color = color;
	}
	};

	this.isSorted = () => this.color === "green";

	this.sorted = () => (this.color = "green");

	this.setValue = (v, color) => {
	if (!this.isSorted()) {
	this.height = v;
	this.setColor(color);
	}
	};
	this.getValue = (v) => this.height;
	}

	const randomArray = shuffledArrayInRange();
	const arrayMembers = randomArray.map((v, i) => {
	return new ArrayMember(10 * i + i, 0, 10, v * 5);
	});

	const drawAll = () => arrayMembers.forEach((m) => m.draw());

	drawAll();

	let ticks = 0;
	const speed = 50;

	bubbleSort(randomArray, (action) => {
	ticks++;
	setTimeout(() => {
	actionsMap[action.type](action, arrayMembers);
	ctx.clearRect(0, 0, innerWidth, innerHeight);
	drawAll(arrayMembers);
	arrayMembers.forEach((m) => m.resetColor());
	}, ticks * speed);
	});

view raw script.js hosted with ❤ by GitHub

And there you have it, we just visualized this cool algorithm in 5 minutes!

Hope you enjoyed this little blog post!

If you liked this visualization, check out some more sorting algorithms visualizations I created.

Check out some of my other blog posts on dev.to

What is Scaffolder, and how you can use it to increase your team dev velocity

Gal Elmalah ・ Jun 11 '20

#tutorial #react #cli #webdev

9 Great Tips To Use Javascript Array Methods Like a Pro!

Gal Elmalah ・ Oct 7 '20

#webdev #javascript #codequality #cleancode

Deploy with ease. Manage efficiently. Scale faster.

Leave the infrastructure headaches to us, while you focus on pushing boundaries, realizing your vision, and making a lasting impression on your users.

Get Started