Lara Schenck

Lover of programming, maker of monsters

Day 6: Algorithms – Sorting Algorithms in JavaScript

Algorithms have got a bad, scary, rap. And you know what? It’s for good reason – understanding an algorithm is pretty doable, but implementing an algorithm in code of your own? It’s hard. I went through writing some common sorting algorithms in JavaScript with lots of help from the Internet. Take a read!

Algorithms are just instructions

In BaseCS, Vaidehi explains algorithms like so:

An algorithm is just fancy term for a set of instructions of what a program should do, and how it should do it. In other words: it’s nothing more than a manual for your code.

Or, the Economist describes them like this:

An algorithm is, essentially, a brainless way of doing clever things. It is a set of precise steps that need no great mental effort to follow but which, if obeyed exactly and mechanically, will lead to some desirable outcome.

Whew! Prior to this foray in computer science, I assumed algorithms were those things other, smarter developers and programmers did, and things that I, the former art student turned developer, was incapable of understanding. It turns out: they are complicated, but I am able to understand (and implement some of) them.

I think the toughest thing about algorithms, particularly in today’s tool-driven ecosystem, is that they are everywhere, but we don’t see them because they are abstracted. We often call a function that executed an algorithm but rarely do we write our own algorithms.

I’m going to focus on sorting algorithms in here.

Sort, sort, sort, sort, sort

In real life, JavaScript’s native Array.prototype.sort() function will get you pretty far. That looks like this:

const array = [1, 1019832, 3, 4, 32, 5, 26, 7, 1, 81, 55, 10];
array.sort((a, b) => { return a - b; });

console.log(array);

But if, like me, you find yourself living not real life, but “learn computer science fundamentals in a very short amount of time” life, writing sorting algorithms yourself in JavaScript is a very useful exercise. And, for what it’s worth, that .sort() function above is actually an implementation of merge sort!

In this post, rather than going through information about the concepts and methods behind sorting, I am going to point you to “Sorting Out The Basics Behind Sorting Algorithms” from, you guessed it, the ever-wonderful BaseCS project from Vaidehi Joshi. So, give that a read, then come back and see how to implement a few sorting algorithms in our favorite (that is, the only) front-end programming language, JavaScript!

I pasted these examples into CodePen for brevity, but I created them in a text editor and ran them using node (node file-name.js in the command line, assuming you have node installed). I found this a better workflow than writing directly in CodePen because I make lots of mistakes with loops, and it’s easier to hit Ctrl+C rather than crashing CodePen tab if you make an oopsie.

Okay, let’s sort!

Bubble sort

With a Big-O time of O(n^2), Bubble Sort is not very performant so not used very often. However, I found implementing it myself to be a good coding exercise, and I learned about using true/false flags in a while loop to determine the end of a program.

In essence, Bubble Sort sorts by comparing an item to the one next to it, and if it’s larger, swap places, if not, go to the next item. Here’s what it would look like in JavaScript with some notes:

See the Pen Bubble Sort in JS by Lara Schenck (@laras126) on CodePen.

I mostly followed this Bubble Sort video on Hacker Rank.

Selection Sort

Selection sort and bubble sort are quite similar except, rather than comparing values only to its neighbor, selection sort compares a minimum item with the rest of the array. Kind of like guessing which is the smallest number, then checking the rest of the array and swapping the guessed minimum with another item that is smaller if it finds one.

I went through the Selection Sort lesson on Khan Academy which was quite helpful. Here’s an adapted version of what the lesson walks you through:

See the Pen Annotated Selection Sort by Lara Schenck (@laras126) on CodePen.

Mergesort

So…my experience with coding this up was that it’s hard. It’s not a lot of code, but it took me a good bit to wrap my brain around it. The concept makes a lot of sense, but I think the implementation didn’t quite match up with it how I’d expected. Anyhow, read on and try for yourself!

Divide and Conquer

This was my first introduction to the theory of “divide and conquer” in algorithms. The idea behind merge sort, as Vaidehi puts it, is that the idea is that sorting two smaller lists then stitching them together is easier than sorting one big list.

So, we will be dividing the array of elements in two, then sorting each individually (or conquering the problem), then stitching them back together for our solution. If we think about that in code, we’ll need functions for both the sorting of each “sub-array” or “sub-problem”, and then a function that combines the two sorted arrays and spits out our final, sorted array.

Multiple ways to merge

Initially, I tried to adapt the code from the Rosetta Code JavaScript version of merge sort like Vaihdehi did in her article, but I ran into a wall. This version by Stoimen rang more true with me. I find it easier to understand building out and returning the result array more literally whereas, in the Rosetta code version, the temporary result array is only stored in memory by way of the function parameter, and is added to by assigning new values to array[i] within the while loops. I kinda get it now, but that confused the sh*t out of me.

Anyhow, here’s complicated-but-kind-of-not merge sort!

See the Pen Annotated Merge Sort in JavaScript by Lara Schenck (@laras126) on CodePen.

Quicksort

Quicksort is similar to merge sort in that they are both divide-and-conquer algorithms. Instead of the sorting happening mainly in the merge process, as in mergesort, quicksort sorts in a different step. Mergesort divides an array in half, in the middle, while quicksort divides at a pivot point, usually an index that is close to the median value.

So, for quicksort:

  1. Divide into subarrays around a pivot element, e.g. in [23, 0, 3, 6, 2, 12, 25, 9], the pivot value could be 6. Then, we have two arrays to sort: [23, 0, 3] and [2, 12, 25, 9].
  2. Conquer the arrays by moving a pointer along each side and comparing values to the pivot value. If either the left value or the right value is larger/smaller than the pivot, swap them.
  3. Recursively repeat this process until the array has been sorted.

See the Pen Annotated Quicksort in JavaScript by Lara Schenck (@laras126) on CodePen.

See this Hacker Rank video on Quicksort.

Okay!

Once again, whew! I’m done for the day. Next up…attempting to apply all of this newfound knowledge to interview practice problems. There is soooo much to know and it is quite overwhelming, but I’m hoping that with these foundations I can at least break down these intimidating whiteboard questions into some form I can work with. We shall see!

Resources:

Lara

, , , , ,