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.
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?)
JavaScript Patterns focuses on patterns used to solve problems in JavaScript. The focus is on the language itself, with only a single chapter dedicated to browser. This is a "quality" book for advanced JavaScript programmers. It presents many of the appropriate patterns unique to doing things the "JavaScript way". It also contains a chapter on traditional object oriented design patterns in JavaScript. (These are covered in a chapter. Some are still useful in JavaScript, while others tend to be more of an academic exercise.) This book was written by somebody that knows their stuff.
Since this book was written in 2010, a lot has changed (and a lot has remained the same.) There are some small tweaks outlined that help gain a few microseconds here and there. Alas, many of these were already being "tweaked" out of the browser as this book was written and are now fairly irrelevant. (The applications that would benefit the most are probably not even going to be able to run in Internet Explorer 6, thus making some of these fixes totally moot.) Other bits are, however, still relevant. I'd put it more on a continuum. Some things are pretty much not worth your effort today. Others are absolutely worthwhile. And in between there are plenty of ideas that may be good in special cases.