At Nixon we make beautiful things and we appreciate the beauty around us. Maybe that’s why Martin Nixon is a patron of the Jubilee pool in Penzance. It’s a pretty bonkers outdoor pool that’s filled by the sea. Yeah, brrrrr. The pool is an art deco sucker punch from the 1930s. You walk through the gate and bam! ART DECO. At any moment you expect to turn a corner and see Agatha Christie sunbathing with chums.
Art deco doesn’t have much to do with computers, but the ideas, execution, straight lines, white-rendered and sharply geometric shapes are reflected in how a computer thinks (or how we tell a computer to think.)
Often there is beauty in the simplicity of an idea. This holds true with algorithms. One of the most common tasks we ask a computer to do is to sort a list of things. There is a bunch of ways that we can do this, but my favourite has to be the Quicksort. It has simplicity that hides complexity.
This is how it works on a list of numbers.
Choose an item in your list, any item. This is your pivot. Next, move all the items ‘less than’ to a left list and all the items ‘more than’ to a right list. Your lists are now slightly more ordered than when we started.
What you do next is really clever. You take the ‘less than’ items (left list) and do the same thing with it. Then you take the ‘more than’ list (right list) and do the same with that.
As you continue chopping your input list into left list, pivot and right list, at some point the input list will be one item which must be in the correct order.
When you have lots of little lists all in the correct order, you simply recombine them: left list + pivot item + right list (your computer knows how to add lists together.) Out pops a sorted list of numbers.
Computers are fun!
Does this work with a list names? Inside your computer everything is a number, a binary number. So, yes, as far as the computer is concerned the letter A is less than the letter B so it can sort names.
2012 will be remembered as the year all computers came with multiple processors (each with multiple cores.) Phones, tablets, laptops, desktops and servers all ship with multiple CPUs inside them. So how does Quicksort, an algorithm from the 1960s, fair in today’s multi CPU world? Actually very well indeed, the list gets chopped and reordered and chopped and reordered, each processor can pick a list to chop and reorder. The more processors you add, the faster it becomes.
Elegant ideas are timeless.
I went all cross eyed reading that! What a great way to introduce the jubilee Pool open day.
Although I would be lying if I said i understood it, i enjoyed reading it. i look forward to the next event in the nixon calendar being announced until then I’ll carry on burnishing my lettraset to the paper with the edge of my ipad.
Nik