Algorithms in a Nutshell: A Practical Guide

A programmer wanted to prevent memory leaks, so he wrote some code to store a record of all memory allocated and freed. However, this code resulted in the programs sometimes taking forever to run. Only after some analysis, it was determined that the binary tree used for storing memory locations was unbalanced, due to the sequential nature of memory allocation in malloc. Balancing the tree reduced the horrible worst-case run times.
This story lead to the promise of a great, practical book on algorithms. Alas, after starting off well, the book soon went of the deep end. Rather than providing simple algorithms to answer real world questions, it dove into deep analysis of algorithms with multiple tables of timings. (Hint: do not use text to speech unless you want to hear endless pronunciations of large numbers.) It went to provide very detailed analysis of implementations of certain algorithms on various platforms. Alas, it only covered a limited number of specific algorithms in this detail. It also went on to cover in significant depth some algorithms with limited use cases. The detail was both too much for a general "nutshell" view of algorithms and not nearly enough for a detailed reference book.

It actually makes sense to implement your own sort

My mantra with algorithms is usually "somebody has probably already done it better." Why implement a sort algorithm if one already exists in your language?

With that it mind, it was a mere academic endeavor to implement Quicksort in JavaScript. I tried populating an array with a million random numbers, fully expecting Array.sort() to blow away my custom quicksort.

But guess what?

It didn't.

I ran some tests in node.js, and Array.sort() always came in last.
Array.sort() converts numbers to strings and then sorts them. For string sorting, it would probably blow away anything you could implement in JavaScript. However, for numbers, a custom sort wins.

Here are the times (in milliseconds) for sorting 1,000,000 integers

array sort (function(a,b) {return a-b;}): 518
quickSort: 235
array sort: 930

The native Array.sort() is the slowest. It returns invalid results with 999 showing up near 9996 since it is a text rather than numeric sort.

Ok, so if you are going to be sorting a huge number of integers, making your own quicksort is the way to go. But if you are looking at strings, the native sort is the way to go, right? Alas, no. For the next sample, I created 1,000,000 strings of 13 random uppercase characters and ran them through our three different scenarios. The quicksort could be used as is (the comparisons work on strings just as well.) The named sort function needed to modified slightly to handle the new sort:


function(a,b) {
if(a<b) { return -1; }
if(b<a) { return 1 };
return 0;
}


In this case, I'm just using capital letters. If there other characters involved (such as umlauts or accents), localeCompare should be used to get more appropriate results.

text sort of text array: 6625
quicksort sort of text array: 4091
named function sort of text array: 5007

Again, quicksort was the fastest, a custom function came in second, and the native sort was last. The percentage difference was not as great as with the integer sort, but the overall time difference was even greater.

The moral of this story: In most cases you will want to use your own sort function for both speed and accuracy. If you are sorting a small number of items, simply plugging a compare function into sort is probably all you need. If there are a large number of items, it would pay to implement your own sort code.

Data Structures and Algorithms with JavaScript

I was hoping this would be a nice advanced JavaScript programming book that would cover implementing common algorithms and data structures in JavaScript. Alas, it is instead geared towards the beginner college student. The coding examples all seem to "work" as stand alone exercises. However, they are coded in a global style that would not allow them to be extended. They use an "Easy to read" object-oriented style that flies in the face of best practices. Many also seem to reinvent the wheel. (Why create a meta-list structure that merely duplicates the pop and push operations found native on an array?)

The algorithms are also quite basic without going into great detail or even providing optimal implementations.

A much better place to look for algorithms and data structures in JavaScript is the Computer Science in JavaScript series of posts by Nick Zakas.