Understanding Quicksort, and taking advantage of JS’s native implementation

color-quicksort Algorithms are a pretty interesting aspect of coding. Of course, they’re not solely part of coding, as the definition states:

Algorithm: a set of rules for solving a problem in a finite number of steps, as for finding the greatest common divisor.

But as a developer, I see algorithms as they pertain to developing systems and applications. What’s interesting about this topic is that when one hears about it, it’s in usually two contexts:

  • CS students that learn all about it and have no idea how to apply them.
  • Developers that implement algorithms and later learn they’re based on already known ones.

I’m in the second category, creating weighted sets of instructions to fulfill some kind of requests. It’s fun especially when you actually understand how the common ones work, why they’re important, and how to implement them in your workflow.

The outdated literature

Explanations today usually involve long drawn out encyclopedic, academic papers or Java/C/Faux code. That type of stuff rarely ever clicks with me and I have a hard time connecting since I rarely ever use Java or C. Fake code isn’t helpful either because it’s mostly stripped C. Seriously. The applications of algorithms are also outdated because they mostly deal with OS, Kernels, or non-applications. It’s time to look at sorts, mergers, and other tasks in terms of web applications.

Why Learn?

In short, speed. The longer explanation is that sooner or later, you’ll naturally find a similar or less performant solution. The usual process goes like this:

  1. intricate use of several “foreach” loops and “while” loops
  2. realization of performance problems
  3. iteration through several solutions to find a better one
  4. repeat several times
  5. realizing that recursion will significantly simplify the problem
  6. go back to step 1

The end result will often either resemble an already existing solution or will resemble a less performant solution. Now, that doesn’t mean you should not experiment. Nor that you should SOLELY use existing common algorithms. They will often not satisfy the problem you’re trying to solve. However, learning how algorithms work, how you can apply them, and what to do with them will help you tackle BIGGER problems.

The Big O

You may have heard of the Big O, or Big Omicron. The Big O is basically a way to describe an algorithms “abstract” performance in operation as the operation’s inputs grow in size toward infinity. The Big O can be further graphed to give you a neat visual representation of how the algorithm will perform under different circumstances.

Big O does not take into effect any factors outside of its mathematical description.

So for instance, certain sorting algorithms can quickly sort an array if that array is under 20 keys but may perform terribly when that array grows into several thousand. Note that Big O does not take into effect any factors outside of its mathematical description. Meaning that anything computer-related is ignored, including the cost of comparisons, the cost of moving elements, accessing memory, or doing whatever else. Big O is used to calculate: best case scenario, worst case scenario, and expected. The latter two are usually used to describe an algorithm. Keep in mind that the Big O gives us the “minimum” at all times.

Part I – Sorting

Sorting algorithms are the basics of the basic. They’re, in my opinion, some of the easiest to grasp and most powerful. Wikipedia has a neat list of them and their Time Complexities.
View on Github

Quicksort first

Let’s start with the simplest, quicksort. Big O The “Big O” time complexity for this one is n log n for average and n^2 for worst. Let’s visualize it. There’s a neat calculator that let’s you compare graphs against each other. Rewritten as a graphic function, we can compare these as y>x * log(x) and y>x*x. graph-1 The blue is the worst case and the red is the best. Basically, the “x” is the number of inputs (the horizontal line) and the “y” is “complexity”, or how much “abstract time” it takes for the algorithm to complete its function. The best case would be if the line stayed constant and VERY low, that’s a dream. What is it? Quicksort is a way of sorting information by splitting the result set recursively. We always pick a pivot (one of the list members) and compare the list against it (less than/greater than) splitting the list into two lists. Each of those goes through the same process until all we’re left with is a fully sorted list. The image all the way above explains the entire process much better than words. Javascript Let’s build this out in Javascript. I’ll be posting these on Github for my “utility belt”. First of all, Javascript’s native .sort() function uses Quicksort. Actually, MOST programming languages use Quicksort as their main sorting mechanism. If you check out jsperf, you’ll find that many have tried to out-do JS’s implementation of quicksort. Just as a sidenote, there are many different code implementation of the algorithm. I personally subscribed to using this one:

  
function quicksort(arr)
{
//if array is empty
if (arr.length === 0) {
return [];
}
  var left = [];
  var right = [];
  var pivot = arr[0];

  //go through each element in array
  for (var i = 1; i < arr.length; i++) {

      if (arr[i] < pivot) {
         left.push(arr[i]);
      } else {
         right.push(arr[i]);
      }
  }

  return quicksort(left).concat(pivot, quicksort(right));
}

At first, it all looks jumbled. Let’s go through it line by line:

  if (arr.length === 0) {
      return [];
  }

  var left = [];
  var right = [];
  var pivot = arr[0];

This first part basically checks if we sent an empty array in, if we did, we’ll return an empty array back. This is crucial to the process. If we don’t respond with an empty array, the process will continue and we’ll be trying to sort nothing, which will result in an error. Next, we’re creating a “left” and a “right” array, if you look at quicksort explanation, you’ll find out that quicksort deals with splitting the results into a “left” and a “right”. The “left” will be smaller than the “pivot” and the “right” will be larger. The pivot is basically a number to use to split the arrays.

  //go through each element in array
  for (var i = 1; i < arr.length; i++) {

      if (arr[i] < pivot) {
         left.push(arr[i]);
      } else {
         right.push(arr[i]);
      }
  }

This loop goes through the entire array (skipping the first element which is our pivot). We make a comparison, if the number for the array is less than the pivot, we send it to the left array. If it’s larger (or equal to) then we send it to the right. And that’s it. The next step is to quicksort the left, add the pivot, and quicksort the right. You’ll probably realize what’s happening. Every number lower than the pivot will be on the left. That array will go through its own quicksort, pushing the lower numbers further left. Once all of the sorting is done, we’ll get an empty array back, and thus go back up the chain until we get to the initial instance of quicksort which will glue a sorted left with the pivot and the sorted right.

Custom quick sort?

Of course, what if you want to sort the array, the other way? Simple, switch the arr[i] < pivot with arr[i] > pivot. But you could also create your own custom comparison. Which brings me back to Javascript’s native sort function. The native .sort() function allows custom comparisons instead of the regular sorting. Javascript uses -1 and 1 markers to specify how a value should be sorted (similar to using true or false). We can rewrite our own function to allow custom sorting like so:

function quicksort(arr, customSort){
   //if array is empty

  if(!customSort) {
    customSort = function(a, b) {
      return a < b;
    };
  }

  if (arr.length === 0) {
    return [];
  }

  var left = [];
  var right = [];
  var pivot = arr[0];

  //go through each element in array
  for (var i = 1; i < arr.length; i++) {

    if (customSort(arr[i], pivot)) {
     left.push(arr[i]);
    } else {
      right.push(arr[i]);
     }
  }

  return quicksort(left).concat(pivot, quicksort(right));
};

Easy. And now, you can use a closure to use a custom sort.

Example custom sort

You may ask, “Well, what will I custom sort anyways?”. Well, by default, javascript’s sort converts all integers into strings, meaning that your results will be alphabetical, not numerical. For instance, if you had an array [0, 2, 1, 10], it would return as [0,1,10,2] as opposed to what you’d expect (my custom quicksort doesn’t do that by the way). Here’s the solution:

[0,2,1,10].sort(function(a, b) { return a - b; });

This function will by pass the stringifying of the integers. There was also another instance that I used custom sorts for and it was while building my popstar cms which required sorting of file names based on their enumeration. The files were named like so 1-title and 2-title. And suffer from the same issue of being alphabetically sorted. On top of that, you can’t just do a a-b since these are string to begin with. I had to use parseInt in order to get the first digits and sort that way:

['1-title', '10-something', '5-other', '15-else'].sort(function(a, b) { return parseInt(a, 10) - parseInt(b, 10); });

ParseInt will automatically grab the first number in the string and discard the rest so that works very well for me :)

V8 Javascript implementation

You can check out how the V8 engine (powers Node and Chromium-based projects) implements arraySort as the sort function. A few things to note:

  • if the array length is 22 or less, insertion sort is used instead.
  • comparison between values is made using a comparefn at all times. Either the built-in one or one that you pass through.
  • there’s no “return” because the function works directly on the dot-delimited array.
  • my compare function uses a true/false method (true goes to the left, false goes to the right), V8 uses a “a-b”, meaning that a negative value goes right and a positive value goes left (if b is bigger than a, it goes right, and the other way around)

Add Your Comment