Sorting

I want to take a break from writing about obscure scala topics and do something a bit more fun - let’s talk about sorting algorithms!

…

So, for everyone that’s still here - yes it really is going to be fun. I get to mess with the essence of javascript - making colourful things move around on screens - and the result is some cool little animations, which I think you’ll enjoy, even if you don’t have a passion for sorting.

To be honest, I don’t have a passion for sorting either. Until writing this, most of the exposure I got to “sorting” as a topic was through people complaining on the internet about software interview questions, where sorting algorithms have a much higher encounter rate than real life.

I’ve had a go at animating a few of them - It’s been fun and I have a genuine appreciation for how everything splurges together at the end of a merge sort.

Quick housekeeping note: I expect the animations will only work on a modern browser, with javascript enabled. If you can’t see a sort of rainbow striped rectangle above the paragraph starting “To be honest”, then something is broken. I’m not saying it’s your fault, but it works fine on my machine. If you do see the rainbow, you can click/poke it to start it moving.

OK, I’m cheating here, these are shuffles rather an sorts. The algorithm moves from left to right, swapping each line with a random one further to the right - the Fisher-Yates shuffle. This algorithm is O(n), so if you wanted to sort twice as many lines, it would take twice as long.

Insertion Sort

To really kick things off, here’s an insertion sort of some colourless vertical bars. (By the way, its extremely satisfying to watch these animations go after spending all this time coding them.)

The algorithm moves through all the lines from left to right. For each line, it compares it with every line to the left until it finds one with a lower value, when it does, it inserts it there. It’s a lot easier to see than to explain. The squares underneath the lines indicate which lines are currently being compared.

Here we have 100 lines with random grey colours. I’ve generated the colours by using RGB values, a greyscale colour is one where all three channels have the same value. rgb(0,0,0) is black, rgb(255,255,255) is white, and everything in between is a nice shade of grey.

The algorithm gets painfully slow as it progresses, because the number of comparisons we have to make grows every time we move a line into position. This is our O(n²) complexity at work.

It’s really easy to sort grey colours, because you can sort them by any of the three channels and you’ll get a result which is very obviously correct.

Things get a lot harder when you allow each channel to be an independent random variable.

Bubble Sort, Merge Sort

I was going to introduce the bubble sort here, but it was so unbearably slow and boring that I don’t think many people would stick around until the end. So the above is a bubble sort, and below is a merge sort on the same criteria. The merge sort rocks by the way.

The bubble sort works by passing through the lines, comparing each with the next. If a pair is out of order, they get swapped, and it moves on to the next pair. It makes repeated passes until everyone is happy. Strangely, it has the same asymptotic complexity as the insertion sort, but in practise it is often much slower (as we see here). Asymptotic behaviour is important, but it isn’t the whole picture.

The merge sort recursively divides the lines in half, until there is only one line in each division. It then combines the divisions in order. This can happen really fast because when you get to combining the larger divisions, we know that they have already been put in order by the previous recursion.

Both of the above line sets are sorted by redness, but they don’t look that great. Why this is the case is complex and fascinating, but we’re talking about sorting, not colours, and it would be weird for me to go into it here. Right?

The Complexity of Sorting Colours

The key point that makes sorting colours so tricky is that they are described in more than one dimension. I’ve been using RGB values, but other systems of defining colours exist, and they all use more than one number to describe each colour. We could visualise them all by running the R, G and B values along the x, y and z axes (hence 3D), but you wouldn’t be able to see them all at once.

It’s really tricky to try and unwind a three dimensional space into a single, ordered line. Well, to be clear, it’s tricky to map them onto an ordered line in such a way that the ordering makes sense.

Imagine trying to describe the area around you now by unravelling it into a line. I know it doesn’t make any sense, but that’s exactly what we’re doing when we try to squish all the colours onto a single scale.

We’re used to thinking of rainbows, which exhibit a nice ordering of the colours (Richard Of York Gave Battle In Vain - although I always thought indigo and violet were too similar to warrant a whole letter). But there are plenty of “colours” which aren’t on the rainbow - our greyscale friends from earlier, for example.

This all helps to explain why the sorting by “redness” looks so bad in the demonstration above. The pure white colour rgb(255,255,255) has way more red in it than most reds - but we as (assumedly) humans can easily tell that a red with rgb(200,10,10) is clearly more red than the white.

It’s clear what’s happening if we can get rid of the noise coming from the green and blue:

Hue, Saturation and Lightness

We might be able to make some progress by switching up our system. RGB makes perfect sense physically, for example, to describe the load on a red, green and blue LED to reproduce these colours in real life, but there are other systems more in tune with the human interpretation of colours.

One of these systems describes the colours by their hue, saturation and lightness (HSL):

  • Hue: which colour is it?
  • Saturation: how strong is the colour?
  • Lightness: how close to black or white is it?

We can transform our RGB values into HSL (source code for this blog is here, don’t judge), and then try sorting our random colours based on the new system. In order, the next three animations will sort by hue, saturation and lightness:

I think these work out a lot better than trying to sort based on RGB values, although we still have the same issue of trying to shrink our three parameters into one value to sort by, the dark and light colours don’t really fit in anywhere when sorting by hue.

We can cheat the sorting process by fixing two of the parameters to be constant - for example, with saturation and lightness both set to 0.5.

For good measure, you can change the saturation and lightness with these old-fashioned sliders.

As an interesting aside (who am I kidding, this whole post is an aside now), if we randomly generate colours by uniformly selecting HSL values, the results are quite different to colours generated from uniform random RGB values. They’re biased against the very vibrant colours we see in the earlier examples. We have inadvertently applied a transformation to the probability distribution of our colours.

By steadily increasing the hue, we can also use HSL to generate more convincing rainbow-ish things (unlike the one I hacked together near the beginning). These last two use the final sort I’m going to the cover, the Quicksort.

Quicksort

Quicksort is similar to the merge sort, but it’s a little harder to see what’s going on. Unlike the merge sort, it doesn’t divide the lines into equal partitions. Instead, it picks a line to be the “pivot” (I just choose the first line), then it partitions all the other lines into those with a lower value and those with higher. The sort is recursively applied to the lower partition, then the higher.

It can look quite different depending on how lucky you get with the pivot - if it ends up being roughly in the middle, then the algorithm can finish in fewer steps. On average it is O(n log n) complexity - which makes sense when you consider that the act of partitioning involves comparing the value of n elements, and we perform the partitioning an average of log n times - as we are roughly dividing the lines in half each time.

A Note on Implementation

It’s really easy to make stuff like this if you know a some basic javascript. The API for drawing shapes onto HTML canvases is incredibly fun to play around with.

The actual animating is all handled by this nifty requestAnimationFrame function, which tells the browser to redraw the canvases. You just tell it what to render, and then line up the next frame and it will run at 60fps.

Here is the code which performs the animation (simplified, but gets the point across):

// Each canvas has it's own rendering engine
function start(engines){
  function renderOnce(timeStamp){
    // Request the next frame.
    // The method renderOnce will be called again at the correct time.
    window.requestAnimationFrame(renderOnce)
    // Run the engine to update all positions
    engines.run()
    // Draw everything
    engines.render()
  }
  // Start running animations
  window.requestAnimationFrame(renderOnce)
}

It looks almost like its doing recursion, but it’s actually a little more involved (this won’t cause a memory leak). It’s nice not to have to worry about timers for simple projects like this.

An engine’s render method might be something like this:

function render(x,y){
  // x and y have been updated by the another method.
  // We need the rendering context for the canvas with ID "ben".
  const ctx = document.getElementById("ben").getContext("2d")
  // Draw a 5x5 red square with top left corner at (x,y).
  ctx.fillStyle = "rgb(255,0,0)"
  ctx.fillRect(x,y,5,5)
}

It’s great fun and pretty intuitive once you get used to it.

It is taxing writing javascript after doing nothing but scala for a pretty long time, I forget what a luxury it is to write some scala code and be confident that it will run exactly as intended, especially once you get a feel for how the compiler works and how to naturally express yourself without fighting it. This is absolutely not the case with javascript, I spent half my time in the debugger trying to work out why lines were disappearing and I see “Cannot read property ‘x’ of undefined” way too often.

I’m sure this wouldn’t be the case if I wrote javascript all the time, but I think there’s always a war on about static vs dynamic typing, and I fall comfortably on the static side.

Having said that, I’ve never written anything this satisfying to watch in scala.