The Magic of Sort in JavaScript (Part 1)

Bubble, Bubble, Toil & Trouble*

I’m halfway through my Software Engineering program at the Flatiron School, and I’ve become increasingly curious about all sorts of higher level concepts. As it so happens, I sort of came upon this TedEd video that presented an interesting question: what’s the fastest way to alphabetize your bookshelf? If you check out the video below, you’ll see that there is an as-sort-ment of ways to sort out the mess, but each method fundamentally deals with a different sorting algorithm.

I have actually never used the phrase “sort out the mess” in a real sentence.

Now that I’ve lost half my readership and got all the terrible puns out of my system, we can dive deeper into how Javascript handles sorting and, more interestingly, take a look at what is going on under the hood of .sort().

According to MDN Web Docs, Javascript’s built-in sorting function is available to all Array objects (think of these as ordered lists). By default, .sort() re-organizes elements of an array by sequentially comparing them by their Unicode point order and swapping the elements in-place as needed.

Exactly.

To unpack the technical definition: .sort() is a function that can be called on any array, each item/element is compared after being converted to a unique number value that corresponds to that character, and swapping happens within the original array itself and not inside a new copy (this has implications on the efficiency and optimization of the sorting process, which we won’t get to until I finish my next module).

It is worth noting that JavaScript’s .sort() function has an optional argument, a compare function, that can be used to modify the standard used in determining the desired order. Two elements (a, b) of the array are passed through to the compare function, and the return value of the compare function (which must be a positive, negative, or zero value) determines whether or not the two elements should swap positions.

Fact: Vanilla is the most boring ice cream flavor, but oddly the only one that can elevate any other dessert (pies, cookies, brownies, etc)

If the return value of the compare function is negative, .sort() will ensure a is at a position before b. (No swap. Results in [a, b])

If the return value of the compare function is zero, .sort() will leave a and b in their own place. They may, however, get shuffled around during later iterations of the sorting process. (No swap. Results in [a, b] until a later comparison)

If the return value of the compare function is positive, .sort() will place a after b. (Swap. Results in [b, a])

Now that we know how sort orders are determined, we can dive into the algorithm within .sort().

~Open your eye~

Algorithms are interesting because everybody’s used the word before, but hardly anyone ever really knows what they are — like foie gras or potpourri. An algorithm in simple terms, is a set of instructions that a computer (our sorting function in our case) follows in executing a desired task. Algorithms are extremely powerful because, given the right commands, computers can complete seemingly Sisyphean tasks with speed and scale.

Algorithms can be pretty complicated to follow, which is why every article I read while researching this topic began by explaining Bubble Sort. Ironically enough, every author seemed to conclude that Bubble Sort is terrible. Un-ironically, I too will do the same:

I know nobody asked, but here it is anyway (title of my eventual autobiography)

Despite its deceptively effervescent name, Bubble Sort is slower than slow. Its biggest drawback is that it does what it does in the way that it does. The Bubble Sort algorithm prescribes instructions as follows:

http://khan4019.github.io/front-end-Interview-Questions/sort.html#mergeSort

1. Begin a loop that is set to run — at most — as many times as there are items in the array.
2. Set a switch (called ‘swapped’) indicating whether a swap was made or not.
3. Create an inner loop that is set to run, at the very least, 1 time less than the length of the array. This is done to ensure that we don’t compare the last item of the array to a non-existent successor. Additionally, the number of runs will be incrementally changing depending on how many times we ran back up to the original loop in step #1. This is done so that we don’t repeat ourselves in checking the largest items that have already made it on to the latter end of the list during previous iterations.
4. Once we’re in the inner loop, check to see if the current item is greater than its successor.
5. If step #4 is true, set the ‘swapped’ switch to true, and switch the items. (Line 7 of the code snippet above is a cool ES6 shorthand for destructuring an array.)
6. Repeat steps 4 and 5 until we meet the limits set by step #3.
7. Check to see if this last run-through made it to the end without any swaps. If swaps were made, then repeat the whole thing back from step #1(this is going to affect the max loops set in step #3 for this loop-through).
8. We get to this step by making it through the max number of loops in step #1 (and consequently step #3), or by clearing the first condition of step #7. In either case, once we hit step #8, our program will return the newly sorted array.

You let me down in Fantasy Football, but thank you for keeping up with this post Randall Cobb

This makes for a terribly inefficient and complex process, earning Bubble Sort an average complexity of O(n*2) (for more on Big O Notation and how algorithm complexities affect run time, check out my friend Billy’s blog post).

However, and thankfully, a computer’s processing speed is faster than our patience is short, so Bubble Sorting works just fine for smaller tasks. Bubble Sort is also okay when sorting through a list that isn’t terribly out of order, which might be useful in running error detections on data that is already sorted for the most part. If an entire loop through the array is passed without any swaps, the Bubble Sort algorithm will know that the sorting process has been completed, whereas more complex sorting algorithms may continue sorting until the entire set has been run through the algorithm.

But even in the things it does right, Bubble Sort is beat out by other algorithms. Insertion Sort has the same ability to stop sorting after a successful run-through of the array without swaps, but with better performance and generally less swaps by completion. Bubble Sort can’t even catch a break on its own Wikipedia page:

“Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.”

Ouch. Owen really doesn’t pull his punches.

Now that we’ve r̶o̶a̶s̶t̶e̶d̶ learned about Bubble Sort as an intro to sorting algorithms, let’s deconstruct the logic behind JS’s sorting magic!

…To be continued in Part 2

Your sorting secrets are safe for one more week, Sorting Hat.

Endnote:
I know the correct line in MacBeth is “Double, Double Toil and Trouble,” but it doesn’t do any good in setting up the punchline for Bubble Sort (welcome to the punchline).