Skip to main content

Ever wondered what an algorithm is?

Algorithms are everywhere. Our children are even taught about them at school, but have you ever found yourself wondering what an algorithm actually is? Maybe you’ve thought they’re something used by computers and created by computer programmers, but don’t really know what they are?

The dictionary defines  an algorithm as:

“A set of rules for solving a problem in a finite number of steps.”

Algorithms come in all shapes and sizes. They can be extremely complicated, but they can also be very simple and easy to understand.

Examples of more complex algorithms include those used to price financial products in a bank or to determine the best route between two points in a satellite navigation system. Simpler algorithms include those used to sort lists of numbers, such as Bubble Sort.

Bubble Sort

Bubble Sort is one of the easiest algorithms to understand. As its name suggests, it’s an algorithm used for sorting. Often the easiest list of things to sort are numbers. Bubble Sort works by comparing each number in the list to the number next to it and swapping them with each other if the numbers are in the wrong order. This process is performed again and again until a pass over the list requires no swaps. At this point the list is sorted. Knowing when to stop sorting the list is just as important as knowing how to sort the list. As we know when to stop (when a pass has no swaps), Bubble Sort can be used for lists of any size.

The easiest way to demonstrate Bubble Sort is with a simple example. Take the list of numbers:

3, 2, 1

We can use Bubble Sort to reverse the list. The first time we pass over the list the first two numbers are 3 and 2. 3 is greater than 2 so we swap them over:

2, 3, 1

Next we compare 3 and 1. 3 is greater than 1, so we swap them over:

2, 1, 3

There are no more pairs of numbers to compare on this pass and there were two swaps (3 & 2 and 3 & 1) so we pass over the list again. The first two numbers on the second pass are 2 and 1. 2 is greater than 1, so we swap them over:

1, 2, 3

Even though we have successfully reversed the list, we’re not finished. Next we compare 2 and 3. 2 is not greater than 3 so we don’t swap them. There are no more pairs of numbers to compare on the second pass and there was a single swap (1 & 3) so we pass over the list again.

1, 2, 3

The first two numbers to compare are 1 and 2. 1 is not greater than 2, so we don’t swap them. Then we compare 2 and 3. 2 is not greater than 3 so we don’t swap them. There are no more pairs of numbers to compare on the third pass and there were no swaps so we’ve finished and successfully reversed the list.


Sorting Algorithms in the Real World

Bubble Sort is taught to trainee software engineers as it’s easy to understand and implement. However, it’s rarely actually used in the real world as it’s inefficient and there are other more efficient sorting algorithms, such as Quicksort, which are only a little more difficult to understand implement.

Sorting occurs in all sorts of systems in the real world. One example is in the software used to sort mail into the order a postman will deliver it as he walks along his round. Postcodes and other address elements are read into the system and sophisticated algorithms used to sort the mail into the correct order.

The next time someone mentions algorithms to you, remember it’s a set of rules for solving a problem in a finite number of steps.

Comments

Popular posts from this blog

Write Your Own Load Balancer: A worked Example

I was out walking with a techie friend of mine I’d not seen for a while and he asked me if I’d written anything recently. I hadn’t, other than an article on data sharing a few months before and I realised I was missing it. Well, not the writing itself, but the end result. In the last few weeks, another friend of mine, John Cricket , has been setting weekly code challenges via linkedin and his new website, https://codingchallenges.fyi/ . They were all quite interesting, but one in particular on writing load balancers appealed, so I thought I’d kill two birds with one stone and write up a worked example. You’ll find my worked example below. The challenge itself is italics and voice is that of John Crickets. The Coding Challenge https://codingchallenges.fyi/challenges/challenge-load-balancer/ Write Your Own Load Balancer This challenge is to build your own application layer load balancer. A load balancer sits in front of a group of servers and routes client requests across all of the serv

Bloodstock 2009

This year was one of the best Bloodstock s ever, which surprised me as the line up didn't look too strong. I haven't come away with a list of bands I want to buy all the albums of, but I did enjoy a lot of the performances. Insomnium[6] sound a lot like Swallow the Sun and Paradise Lost. They put on a very good show. I find a lot of old thrash bands quite boring, but Sodom[5] were quite good. They could have done with a second guitarist and the bass broke in the first song and it seemed to take ages to get it fixed. Saxon[8] gave us some some classic traditional heavy metal. Solid, as expected. The best bit was, following the guitarist standing on a monitor, Biff Bifford ripped off the sign saying "DO NOT STAND" and showed it to the audience. Once their sound was sorted, Arch Enemy[10] stole the show. They turned out not only to be the best band of the day, but of the festival, but then that's what you'd expect from Arch Enemy. Carcass[4] were very disappoin

Catalina-Ant for Tomcat 7

I recently upgraded from Tomcat 6 to Tomcat 7 and all of my Ant deployment scripts stopped working. I eventually worked out why and made the necessary changes, but there doesn’t seem to be a complete description of how to use Catalina-Ant for Tomcat 7 on the web so I thought I'd write one. To start with, make sure Tomcat manager is configured for use by Catalina-Ant. Make sure that manager-script is included in the roles for one of the users in TOMCAT_HOME/conf/tomcat-users.xml . For example: <tomcat-users> <user name="admin" password="s3cr£t" roles="manager-gui, manager-script "/> </tomcat-users> Catalina-Ant for Tomcat 6 was encapsulated within a single JAR file. Catalina-Ant for Tomcat 7 requires four JAR files. One from TOMCAT_HOME/bin : tomcat-juli.jar and three from TOMCAT_HOME/lib: catalina-ant.jar tomcat-coyote.jar tomcat-util.jar There are at least three ways of making the JARs available to Ant: Copy the JARs into th